Skip to content

线段树 Segment Tree

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

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

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

void set(int k, int x) {  // 更新元素k为x
  k += n;
  tree[k] = 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。

习题