1. 线段树

对于一个给定的数组 \(arr\), 对这个数组中的元素进行若干次如下操作:

1. 根据给定的 \(l\), \(r\), \(v\), 将 \(arr\) 中的 \([l, r]\) 区间的元素 \(+1\)
2. 根据给定的 \(l\), \(r\), 输出 \(arr\) 中的 \([l, r]\) 区间的元素和/积/差/最大值/最小值(这里以和为例)

关于第一个操作, 我们很容易想到差分, 其只需要 \(O(n)\) 的预处理, 即可以 \(O(1)\) 的操作将区间的元素 \(+1\)
关于第二个操作, 我们也很容易想到前缀和, 同样只需要 \(O(n)\) 的预处理时间, 就能够以 \(O(1)\) 的时间复杂度获取一个区间的和

然而, 对于这个问题的两个操作的复合, 是差分/前缀和解决不了的. 于此, 引出线段树这个数据结构. 通过线段树, 可以做到以 \(O(logn)\) 的时间进行区间统计和操作

1.1 线段树是什么

上图中, 是对一个有着 7 个元素的数组建立的线段树:

• 其叶子节点表示着每个元素所对应的具体的值
• 每个非叶节点都表示着对应的区间的一种表示方法(和/积/差/最大值/最小值...)

当需要对一个区间进行求和时, 例如区间 \([2, 6]\), 只需要获取 5, 6, 7 节点的值即可. 而获取每个节点值所需要的时间复杂度为 \(O(logn)\)

1.2 建树

这里线段树的下标从 1 开始(当然也可以从 0 开始)

int arr[N];
int tree[N << 2];

// u 表示当前节点, l 和 r 表示对 arr 数组的建树区间
void build(int u, int l, int r) {
  // 当 l == r 时, 说明已经是叶节点了
  // 直接将数组中对应下标元素的赋值给线段树的对应节点即可
  if (l == r) { tree[u] = arr[l]; return; }
  
  // 防止 l + r 溢出
  int m = l + (r - l >> 1); 
  build(u << 1, l, m);
  build(u << 1 | 1, m + 1, r);

  // 将两颗子树建好后应获取两个子树区间的和
  tree[u] = tree[u << 1] + tree[u << 1 | 1];
}

1.3 查询

对于要查询的区间 \([ql, qr]\) 和 当前节点 \(u\) 所对应的区间 \([l, r]\), \(u\) 节点所表示的区间的中点 \(m = \lfloor \frac{l + r}{2} \rfloor\)

• \([l, r] \subseteq [ql, qr]\), 表示整个节点所表示的区间都在直接返回该节点的值
• \(l \leq m\), 表示要查询的区间在该节点的左子节点中存在, 递归查询其左子节点
• \(r > m\), 表示要查询的区间在该节点的右子节点中存在, 递归查询其右子节点

int query(int u, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return tree[u];

  int m = l + (r - l >> 1), sum = 0;

  if (ql <= m) sum += query(u << 1, l, m, ql, qr);
  if (qr > m) sum += query(u << 1 | 1, m + 1, r, ql, qr);

  return sum;
}

1.4 区间修改

我们知道, 对于线段树来说, 寻找其每一个节点所需要的时间都是 \(O(logn)\). 如果每一次区间修改都对所有对应节点进行修改的话, 一次区间修改需要 \(O(nlogn)\), 必然是超时的
所以, 这里使用了一种 懒标记法, 即每一次修改在非必要的情况下只会更新区间, 而不会落实到具体的区间. 待到以后再次查询或修改时更新

我们假设上图的数组 \(arr = \{0, 1, 2, 3, 4, 5, 6\}\)

• 我们对区间 \([1, 6]\) 进行区间 \(+2\) 操作
  
  可以发现, 对于一个区间的操作, 如果没有具体到一个叶节点的话(如上图的叶节点 9), 其只会更新其区间节点, 并在节点中添加一个懒标记(如上图的节点 3), 以供以后查询对应元素(节点 3 的子节点)时顺带将操作下放, 如下面的例子
• 对区间 \([5, 6]\) 进行查询操作
  
  因为会从节点 3 一直查询到其下两层节点, 所以节点 3 的下两层节点都会被其懒标记更新, 同时, 节点 3 的懒标记也会恢复

// 懒标记数组
int lazy[N << 2];

void modify(int u, int v, int n) {
  tree[u] += n * v;
  lazy[u] += v;
}

void pushDown(int u, int l, int r) {
  int m = l + (r - l >> 1);

  modify(u << 1, lazy[u], m - l + 1);
  modify(u << 1 | 1, lazy[u], r - m);

  lazy[u] = 0;
}

// v 表示对 [ql, qr] 区间的更新操作所对应的值
void update(int u, int l, int r, int ql, int qr, int v) {
  if (ql <= l && qr >= r) return modify(u, v, r - l + 1);

  // 将懒标记下放, 更新该节点所对应的子节点
  pushDown(u, l, r);

  int m = l + (r - l >> 1);
  if (ql <= m) update(u << 1, l, m, ql, qr, v);
  if (qr > m) update(u << 1 | 1, m + 1, r, ql, qr, v);

  tree[u] = tree[u << 1] + tree[u << 1 | 1];
}

如此, 需要对 query 添加懒标记下放操作

int query(int u, int l, int r, int ql, int qr) {
  if (ql <= l && qr >= r) return tree[u];

  pushDown(u, l, r);
  int m = l + (r - l >> 1), sum = 0;
  if (ql <= m) sum += query(u << 1, l, m, ql, qr);
  if (qr > m) sum += query(u << 1 | 1, m + 1, r, ql, qr);

  return sum;
}