线段树segmentTree，这里有你需要知道的一切要点

封面图和文无关，笔者写这篇博客时正好在听～

一、线段树存在的意义#

线段树是一种维护区间信息的数据结构，它可以将包括 单点修改、区间修改、区间查询 为主的一类操作的时间复杂度控制在 $O(logn)$ 内。

二、线段树原理#

线段树是一种 二叉搜索树。它运用了一种分治类的思想，对于满足 区间加法 类问题，都可以通过不断拆分为更小的子问题，直到子问题可以直接被解决。

Note

什么是区间加法？
一个问题满足区间加法，仅当对于区间 [L,R] 的问题的答案可以由 [L,M] 和 [M+1,R] 的答案合并得到。

线段树的设计思路可以用如下流程图来表示，对于一个长度区间为 $[1,10]$ 的问题，通过不断分治拆分，最多可以拆分成如图所示的最小长度为 1 的子问题。
线段树素材

为了解决实际问题，我们引入一个value变量代表区间内元素的和（假定元素都是整数类型，和的范围在 long long 内）。

建树代码实现#

#define range 100000;
long long values[range];//模拟一个区间
struct node{
  int l, r;
  int value;
  int lazy;//懒标记，用于控制区间修改，后面会讲
}node[4 * range];//树的最大长度为 4 * range
void push_up(int i){
  node[i].value = node[i << 1].value + node[i << 1 | 1].value;
}
/**
  * @param 
  i: Current tree's root 代表当前建树的根节点
  l: Current node's left interval 当前节点区间左侧
  r: Current node's right interval 当前节点区间右侧
  */
void build(int i, int l, int r){
  node[i] = { l, r, 0, 0 };
  //已经是最小区间
  if（l == r){
    node[i].value = values[l];
    return ;
  }
  int mid = (l + r) >> 1;
  build(i << 1, l, mid);
  build(i << 1 | 1, mid + 1, r);
  push_up(i);
  return node[i].value;
}

三、线段树操作#

上文提到，线段树设计出来是为了完成区间操作，其中增删改查只能完成 改 (modify) 和查 (query) 操作。

区间查询#

查询操作十分简单，给定查询区间 $[l, r]$ ，从根节点开始向下查找，如果节点区间落在查询区间内，加上其 value；否则如有交集，继续查询子节点。

long long query(int i,int l,int r){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  int mid = (rangeL + rangeR) >> 1;
  int ans = 0;
  if(l <= rangeL && r >= rangeR){
    return node[i].value;
  }
  //和左侧子区间有交
  if(l <= mid){
     ans += query(i << 1, l, r);
  }
  //和右侧子区间有交
  if(r > mid){
     ans += query(i << 1 | 1, l, r);
  }
  return ans;
}

修改#

先说单点修改。单点修改是从根元素的 dfs，找到目标点即可。需要注意的是路径上所有节点都要同步修改。

void point_modify(int i, int target, int k){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  if(rangeL == rangeR){//找到目标点
    node[target].value += k;//操作自定
  }
  int mid = (rangeL + rangeR) >> 1;
  if(target <= mid){
    modify(i << 1, target, k);
  }
  else{
    modify(i << 1 | 1, target, k);
  }
  //修改路径
  push_up(i);
}

区间修改肯定不能沿用这种操作，否则修改的时间复杂度来到 $O(nlogn)$ ，不可接受。
于是设计一种方法，在查找过程中只查找到大的区间而不查找到最小节点，并且附上一个变量 lazytag 保存修改值。需要操作区间子集时，再下传 lazytag 修改子区间值。
代码实现：

void push_down(int i, int l, int r){
  if(node[i].lazy){
    int mid=(l+r)>>1;
    node[i<<1].lazy = node[i].lazy;
    node[i<<1|1].lazy = node[i].lazy;
    //下传懒标记
    node[i<<1].value += node[i].lazy * (mid - l + 1);
    node[i<<1|1].value += node[i].lazy * (r - mid);
    //更新值
    node[i].lazy = 0;
  }
}

void range_modify(int i, int l, int r, int k){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  if(l >= rangeL && r <= rangeR){
    node[i].lazy = k;
    node[i].value += k * (r - l + 1);
    return ;
  }
  //将子节点修改传下去
  push_down(i, rangeL, rangeR);
  int mid = (rangeL + rangeR) >> 1;
  if(l <= mid){
    range_modify(i << 1, l, r, k);
  }
  if(r > mid){
    range_modify(i << 1 | 1, l, r, k);
  }
  //修改路径
  push_up(i);
}

long long range_query(int i,int l,int r){
  int rangeL = node[i].l;
  int rangeR = node[i].r;
  //要查询子节点，将lazytag传下去
  push_down(i, rangeL, rangeR);
  int mid = (rangeL + rangeR) >> 1;
  int ans = 0;
  if(l <= rangeL && r >= rangeR){
    return node[i].value;
  }
  //和左侧子区间有交
  if(l <= mid){
     ans += range_query(i << 1, l, r);
  }
  //和右侧子区间有交
  if(r > mid){
     ans += range_query(i << 1 | 1, l, r);
  }
  return ans;
}

Done！#

Tip

可以在luogu 模板题 1中尝试你学到的知识。
以上代码不保证 AC。