线段树基本原理和操作

线段树的一些基本操作和原理：

由二分的思想而来，一段区间划分，实现大量数据的查询删除O(log(n))

线段树（英语：Segment tree）是一种二叉树形数据结构，1977年由Jon Louis Bentley发明，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。

---

基本操作：

1. 构建线段树

   struct node
   {
       int l,r,w,f;
   }tree[401];//四倍空间才够
   int n,p,a,b,m,x,y,ans;
   void build(int l,int r,int k)//l~r的区间,从k开始
   {
       tree[k].l=l;tree[k].r=r;
       if(l==r){cin>>tree[k].w;return;}//到达最后一层就输入数据
       int m=l+r>>1;//否则进行二分划分区间
       build(l,m,k*2);build(m+1,r,k*2+1);//左建右建
       tree[k].w=tree[k*2].w+tree[k*2+1].w;//状态合并
   }
   //就是不断递归建立线段树
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14

---

2. 单点查询

   void ask(int k)//单点查询
   {
       if(tree[k].l==tree[k].r){ans=tree[k].w;return;}//当前结点的左右端点相等，是叶子节点，是最终答案 
       //否则二分查找区间
       int m=(tree[k].l+tree[k].r)/2;//目标位置比中点靠左，就递归左孩子
       if(x<=m)ask(k*2);else ask(k*2+1);//否则递归右孩子
   }
   1
   2
   3
   4
   5
   6
   7

---

3. 单点修改

   //结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态
   void add(int k)
   {
       if(tree[k].l==tree[k].r)//找到目标位置 
       {tree[k].w+=y; return;}
       int m=(tree[k].l+tree[k].r)/2;
       if(x<=m) add(k*2);
       else add(k*2+1);
       tree[k].w=tree[k*2].w+tree[k*2+1].w;//所有包含结点k的结点状态更新 
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

---

4. 区间查询

   void sum(int k)
   {
       if(tree[k].l>=x&&tree[k].r<=y) 
       {
           ans+=tree[k].w;
           return;
       }//包含了直接加上
       int m=(tree[k].l+tree[k].r)/2;
       if(x<=m) sum(k*2);//左孩子
       if(y>m) sum(k*2+1);//右孩子
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11

---

5. 区间修改（利用lazy标记法）

   void down(int k)
   {
       tree[k*2].f+=tree[k].f;
       tree[k*2+1].f+=tree[k].f;
       tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
       tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
       tree[k].f=0;
   }//下传操作
   void add(int k)
   {
       if(tree[k].l>=a&&tree[k].r<=b)//当前区间全部对要修改的区间有用 
       {
           tree[k].w+=(tree[k].r-tree[k].l+1)*x;//(r-1)+1区间点的总数
           tree[k].f+=x;
           return;
       }
       if(tree[k].f) down(k);//懒标记下传。只有不满足上面的if条件才执行，所以一定会用到当前节点的子节点 
       int m=(tree[k].l+tree[k].r)/2;
       if(a<=m) add(k*2);
       if(b>m) add(k*2+1);
       tree[k].w=tree[k*2].w+tree[k*2+1].w;//更改区间状态 
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22

参考链接:浅谈线段树