转载

线段树讲解（数据结构、C++）

声明：

仅一张图片转载于 http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html ，自己画太麻烦了。。。那个博客的讲解也很好，只是他用了指针的方式来定义线段树，而我用了结构体，并且他讲了线段树的更高级的操作，若对线段树的初级操作不理解，请继续阅读

线段树作为一种十分常用的数据结构，在NOIP、NOI中广泛的出现，所以在这里对线段树进行简单的讲解。

线段树支持对一个数列的求和、单点修改、求最值（最大、最小）、区间修改（需要lazy标记，暂不讲解）。这几种操作，时间复杂度是（logn）级别的，是一种十分优秀的数据结构。因此其获得了广泛的应用。

定义：顾名思义，它是一种树形结构，但每段不是平常所学的一个点一个点的树，而是一条一条的线段，每条线段包含着一些值，其中最主要的是起始和结束点记作 l，r 即左端点和右端点。

那么该如何划分线段树呢？我们采用二分的思想，即每次将一段取半，再进行接下来的操作，这样综合了操作的方便程度和时间复杂度。因为线段树通过二分得来，所以线段树是一颗二叉树。这也方便了对儿子查找。下面是线段树的图，有利于理解：

线段树讲解（数据结构、C++）

建树：仅仅知道模型还是不够的，建树的过程是线段树的关键（build(1,1,n)）从一号开始，左端是1，右端是n

位运算 i<<1 等效于 i/2 (i<<1)|1 等效于 i/2+1 加速。。。

inline void update(int i)更新i节点维护的值（求和，最大……）  {      node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum;      node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx);  }  inline void build(int i,int l,int r)//inline 还是加速  {        node[i].l=l;node[i].r=r;//左右端点为当前递归到的 l 和 r            if(l==r){//若l==r 则当前的树节点是真正意义上的点           node[i].maxx=a[l];//最大值就是本身的值           node[i].sum=a[l];//区间的和就是本身的值          return;        }        int mid=(l+r)/2;//因为是二叉树所以以中点为分割点         build(i<<1,l,mid);//根据二叉树的知识，左儿子是i/2右儿子是i/2+1         build((i<<1)|1,mid+1,r);        update(i); }

数列求和：这是线段树的一个典型算法，其他的很多应用都是从中转化的。

为了求和我们定义一个函数sum(int i ,int l ,int r ) i 是开始的树节点，我们默认为1。 l 是区间的开始点，它的标号是在数列中的标号， r 是结束点其余同 l 。帖下代码：

inline int sum(int i,int l,int r)//inline 又是加速    {                                                    if(node[i].l==l&&node[i].r==r)     return node[i].sum;//若树节点的左右区间与查找区间相同，返回其维护的sum     int mid=(node[i].l+node[i].r)/2;//确定该树节点的中点以确定继续查找左儿子还是右儿子        if(r<=mid) return sum(i<<1,l,r);//若查找区间最右端小于中点，则该区间完全包含于左儿子中      else if(l>mid) return sum((i<<1)|1,l,r);//最左端大于中点，查找右儿子        else return sum(i<<1,l,mid)+sum((i<<1)|1,mid+1,r)       //若跨越中点，查找左儿子 l 到 mid ,和右儿子的 mid+1 到 r 并返回值  }

区间求最值和区间求和大致相同，自己看一下

inline int Max(int i,int l,int r) {     if(node[i].l==l&&node[i].r==r)      return node[i].maxx;     int mid=(node[i].l+node[i].r)/2;     if(r<=mid) return Max(i<<1,l,r);       else if(l>mid) return Max((i<<1)|1,l,r);         else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r)); }

单点更新：和区间不同，但基本思想还是一样的。

inline void add(int i,int k,int v)//当前计算到的点为i，把数列中的第k个元素加v {  if(node[i].l==k&&node[i].r==k){//因为更改的单点，所以左右端点均和k相等   node[i].sum+=v;   node[i].maxx+=v;   return;  }  int mid=(node[i].l+node[i].r)/2;  if(k<=mid) add(i<<1,k,v);//若k小于mid则k在树节点i的左子树中   else add((i<<1)|1,k,v);//反之  update(i);//更新 }

最后贴下全部的代码基本可以做模板了。。

#include<iostream> #include<cstdio> using namespace std; struct tree{  int l,r,sum,maxx; }; tree node[100]; int n,m,a[100]; inline void update(int i) {  node[i].sum=node[i<<1].sum+node[(i<<1)|1].sum;  node[i].maxx=max(node[i<<1].maxx,node[(i<<1)|1].maxx); } inline void build(int i,int l,int r) {  node[i].l=l;node[i].r=r;  if(l==r){    node[i].maxx=a[l];    node[i].sum=a[l];    return;  }   int mid=(l+r)/2;  build(i<<1,l,mid);  build((i<<1)|1,mid+1,r);  update(i); } inline void add(int i,int k,int v) {  if(node[i].l==k&&node[i].r==k){   node[i].sum+=v;   node[i].maxx+=v;   return;  }  int mid=(node[i].l+node[i].r)/2;  if(k<=mid) add(i<<1,k,v);   else add((i<<1)|1,k,v);  update(i); } inline int sum(int i,int l,int r) {  if(node[i].l==l&&node[i].r==r)   return node[i].sum;  int mid=(node[i].l+node[i].r)/2;  if(r<=mid) return sum(i<<1,l,r);   else if(l>mid) return sum((i<<1)|1,l,r);     else return sum(i<<1,l,mid)+sum((i<<1)|1,mid+1,r); } inline int Max(int i,int l,int r) {  if(node[i].l==l&&node[i].r==r)   return node[i].maxx;  int mid=(node[i].l+node[i].r)/2;  if(r<=mid) return Max(i<<1,l,r);    else if(l>mid) return Max((i<<1)|1,l,r);   else return max(Max(i<<1,l,mid),Max((i<<1)|1,mid+1,r)); } int main() {  scanf("%d%d",&n,&m);  for(int i=1;i<=n;i++)  scanf("%d",&a[i]);  build(1,1,n);  for(int i=1;i<=m;i++){   int c,a,b;   scanf("%d%d%d",&c,&a,&b);   if(c==1) printf("%d/n",sum(1,a,b));     else if(c==2) add(1,a,b);    else if(c==3) printf("%d/n",Max(1,a,b));  }  }