线段树

定义

  线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于每一个子节点而言，都表示整个序列中的一段子区间；

  对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。 线段树维护的问题必须满足区间加法。(一个问题满足区间加法，仅当对于区间[L,R]的问题的答案可以由[L,M]和[M+1,R]的答案合并得到。)

实现

以区间求和为例,用线段树维护 数组a[9,3,-1,8,4,-2] (下标从1开始

储存

用数组模拟树。区间[L,R]，w表示维护的数据，lazy为懒惰标记。

struct node
{
 int L,R,w,lazy;
}tree[maxn];

建树

目前不用关心lazy

通过图片可以得到一些信息：

① 本例中，数组大小为6,线段树大小为13。(tree[10],tree[11]没有用到)，所以线段树一般应该开4*n大小，防止RE。

② tree[k]的孩子节点为tree[2k],tree[2k+1]

③ 叶子节点tree[8].w, tree[9].w, tree[5].w, tree[12].w, tree[13].w, tree[7].w为原数组对应的值。父节点.w为子节点.w的和。

代码

void build(int L,int R,int k)   
{
  tree[k].L=L; tree[k].R=R; tree[k].lazy=0;
  if(tree[k].L==tree[k].R)
  {
    scanf("%d",&tree[k].w);
    return;
  }
  int m=(L+R)/2;
  build(L,m,k*2);
  build(m+1,R,k*2+1);
  tree[k].w=tree[k*2].w+tree[k*2+1].w;
}

单点查询

目前不用关心lazy

代码

void ask_point(int L,int R,int l,int r,int k)
{
  if(tree[k].L==tree[k].R)
  {
    printf("%d",tree[k].w);
    return ;
  }
  if(tree[k].lazy) down(k);
  int m=(L+R)/2;
  if(l<=m) ask_point(L,m,l,r,k*2);
  else ask_point(m+1,R,l,r,k*2+1);
}

单点修改

目前不用关心lazy

单点修改和单点查询大同小异

代码

void change_point(int L,int R,int l,int r,int k,int add)
{
  if(tree[k].L==tree[k].R)
  {
    tree[k].w+=add;
    return;
  }
  if(tree[k].lazy) down(k);
  int m=(L+R)/2;
  if(l<=m) change_point(L,m,l,r,k*2,add);
  else change_point(m+1,R,l,r,k*2+1,add);
  tree[k].w=tree[k*2].w+tree[k*2+1].w; 
}

区间查询

目前不用关心lazy

代码

void ask_interval(int L,int R,int l,int r,int k,int &ans) 
{
  if(tree[k].L>=l&&tree[k].R<=r) 
  {
    ans+=tree[k].w;
    return;
  }
  if(tree[k].lazy) down(k);
  int m=(L+R)/2;
  if(l<=m) ask_interval(L,m,l,r,k*2,ans);
  if(r>m) ask_interval(m+1,R,l,r,k*2+1,ans);
}

区间修改

巧用Lazy！！！

发现了一个“错误”，线段树应该满足区间加法，也就是说tree[k].w=tree[2k].w+tree[2k+1].w，但是图片中tree[3].w!=tree[6].w+tree[7].w,16!=12+(-2)，与此同时tree[3].lazy=2。因为tree[3].w的意义为区间[4,6]的和，也就是a[4],a[5],a[6]的和，操作为区间[3,6]都加2，也就是a[4], a[5], a[6],都加2，也就是tree[3].w+6=16。

那怎么得到tree[6]，tree[7]，tree[12]，tree[13]，正确的状态呢？

可以注意到每个函数里都有 if(tree[k].lazy) down(k)，它的作用就是使线段树维护正确的数据。

在进行函数操作时，会顺便将lazy标记下传。

比如，你访问tree[6]的状态时，肯定会经过被lazy标记过的tree[3]，这时候通过标记下传，得到tree[6]正确的状态。

代码

void change_interval(int L,int R,int l,int r,int k,int add) 
{
  if(tree[k].L>=l&&tree[k].R<=r)
  {
    tree[k].w+=(tree[k].R-tree[k].L+1)*add;
    tree[k].lazy+=add;
    return;
  }
  if(tree[k].lazy) down(k);
  int m=(L+R)/2;
  if(l<=m) change_interval(L,m,l,r,k*2,add);
  if(r>m) change_interval(m+1,R,l,r,k*2+1,add);
  tree[k].w=tree[k*2].w+tree[k*2+1].w;
}

可以看到tree[3].lazy进行了标记下传，使得tree[3].lazy又变回了0，tree[6].lazy=2, tree[7].lazy=2。然后tree[6].w=tree[6].w+2*2=16,tree[7].w=tree[7].w+2=0。

所以每个函数中的下传函数都要写在递归函数之前，这样才能正确维护数据。

下传函数

void down(int k) 
{
  tree[k*2].lazy+=tree[k].lazy;
  tree[k*2+1].lazy+=tree[k].lazy;
  tree[k*2].w+=tree[k].lazy*(tree[k*2].R-tree[k*2].L+1);
  tree[k*2+1].w+=tree[k].lazy*(tree[k*2+1].R-tree[k*2+1].L+1);
  tree[k].lazy=0;
}