线段树 Segment Tree

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

以区间求和问题为例，对$a={10,11,12,13,14}$建立以下线段树:

单点修改，区间查询

单点修改，区间查询（经常简称PURS，Point Update Range Sum）是线段路的最基本也是最重要的形态，要牢固掌握和应用。

实现

很多教程上线段树都是用递归来实现的，这导致函数参数众多（5个参数或更多），不容易记忆，而且执行效率并不高。实际上通过简单的位运算，线段树实现可以大大简化，不但效率高，而且更容易理解和记住。例如对于求和问题可以实现如下（来自CPH 9.3）：

void set(int k, int x) {  // 更新元素k为x
  k += n;
  tree[k] = x;            // 改成 += x，就可以变成增量修改
  for (k /= 2; k >= 1; k /= 2) {
    tree[k] = tree[2*k]+tree[2*k+1];
  }
}
 
int sum(int a, int b) { // 返回区间[a,b]的和
  a += n; b += n;
  int s = 0;
  while (a <= b) {
    if (a%2 == 1) s += tree[a++]; // 左边界如果是右子树，则合并进结果，并右移
    if (b%2 == 0) s += tree[b--]; // 右边界如果是左子树，则合并进结果，然后左移
    a /= 2; b /= 2;
  }
  return s;
}
 

这个代码对于任意n都是可以的。

AI.Cash的文章Efficient and easy segment trees讲得很清楚，包括高效实现（如上不用递归 ），区间修改、lazy propagation等。

区间修改

更进一步线段树，比如区间修改、堆式建树，见OI-Wiki。

习题