介绍

线段树（Segment tree）是一种二元树形资料结构，用以储存区间或线段。

线段树可以在  O(logN) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值/最小值）等操作。

非常棒的介绍：https://oi-wiki.org/ds/seg/ （不过这里面有一些错误，评论区有不少人也提到了，我在下面的笔记中都修正了）

有个大小为 5 的数组a={10,11,12,13,14} ，要将其转化为支持区间求和的线段树，有以下做法：设线段树的根节点编号为 1，用数组  d 来保存我们的线段树， d[i]用来保存线段树上编号为 i 的节点的值（这里每个节点所维护的值是这个节点所表示的区间总和）。

一般采用堆式存储：即用一个数组来储存树结构，d[i]的左儿子节点是 d[2*i]，右儿子节点是 d[2*i+1]

如果懒得计算线段树一共有多少个节点，可以直接把数组长度设为 4n

实现

建树build

void build(int s, int t, int p) {
  // 对 [s,t] 区间建立线段树,该区间节点编号为 p
  if (s == t) {
    d[p] = a[s];
    return;
  }
  int m = s + ((t - s) >> 1);
  // 移位运算符的优先级小于加减法，所以加上括号
  // 如果写成 (s + t) >> 1 可能会超出 int 范围
  build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
  // 递归对左右区间建树
  d[p] = d[p * 2] + d[(p * 2) + 1];
}

查询query（不使用懒惰标记）

int getsum(int l, int r, int s, int t, int p) {
  // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
  if (l <= s && t <= r)
    return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和

  int m = s + ((t - s) >> 1), sum = 0;

  if (l <= m) sum += getsum(l, r, s, m, p * 2);
  // 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子

  if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
  // 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子

  return sum;
}

区间修改update

要修改区间[l,r]，那么就把所有包含在区间[l,r]中的节点都遍历并修改一次