线段树基础详解，如何深入掌握？

1.简介 线段树，顾名思义，就是由线段构成的树，是一个较为优秀的数据结构，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，通常用于解决区间类的问题，在各大OI赛事中频繁出现。下面我将为你展示线段树的一些基本操作及原理 2.存储 线段树一般用结构体存储，代码如下： struct node{ int l,r,num,add; }tree[10010]; //add 用于懒标记 3.建树 代码如下： void buildtree(int x,int y,int p){ t[p].l = x,t[p].r = y; if (x == y){ t[p].sum = a[x]; return; } int mid = x+y>>1; buildtree(x,mid,p<<1); buildtree(mid+1,y,(p<<1)+1); t[p].sum = t[p<<1].sum+t[(p<<1)+1].sum; } 4.懒标记 从前有一个人，太懒了，修改线段树区间值时不想把线段树全都遍历一遍，于是就有了懒标记 懒标记的精髓就是打标记和下传操作，由于我们要做的操作是区间加一个数，所以我们不妨在区间进行修改时为该区间打上一个标记，就不必再修改他的儿子所维护区间，等到要使用该节点的儿子节点维护的值时，再将懒标记下放即可，可以节省很多时间，对于每次区间修改和查询，将懒标记下传，可以节省很多时间。当然，这一操作不是必要的，在不住求代码运行速度的时候可以不用 代码如下： void tag(int p){ if (t[p].add){ //如果懒标记不为空，则进行下传操作 t[p<<1].sum += t[p].add*(t[p<<1].r-t[p<<1].l+1); //这里，因为luogu的模板题中修改是对于区间内每一个值的所以是乘 t[(p<<1)+1].sum += t[p].add*(t[(p<<1)+1].r-t[(p<<1)+1].l+1); t[p<<1].add += t[p].add; t[(p<<1)+1].add += t[p].add; t[p].add = 0; } } 5.区间修改 从根节点自上而下查找，当发现有区间覆盖要修改的节点时，我们就把这一区间修改并打上懒标记。否则下传懒标记，继续查找。