Tommy Chen home

线段树

20 Sep 2025

1. 简介

2. 原理及实现

线段树是一种二叉树；除最底层外，其结构是一棵完全二叉树。每个节点代表一个区间，最底层节点代表单个元素。父节点可由子节点计算得到，例如求和或取最大值。

p1
图1

如图 1 所示，线段树维护数组 [10, 11, 12, 13, 14]，父节点由子节点求和得到。

不难发现，一个二叉树中，对于第n个节点，其左子节点编号为2n，右子节点编号为 2n+1。

2.1 建树

void build(int p, int pl, int pr) { // 当前节点标号，以及其对应区间
        if(pl == pr) {
                    tree[p] = a[pl]; // 抵达最底层，赋值
                    return;
        }
        int mid = (pl + pr) / 2;
        build(2*p, pl, mid);
        build(2*p+1, mid+1, pr);
        tree[p] = tree[2*p] + tree[2*p+1]; // 重要赋值语句
}

采用递归的方法，从根节点开始，函数每次都向下一级传入当前节点编号、当前节点对应的区间。因此以如下形式调用。

build(1, 1, n);

当递归到二叉树最底层时停止。判断条件是当前节点对应的区间长度为 1（左端点等于右端点）；此时为叶节点赋值。

若还未到树的最底层，那么就开始向两个子节点递归，传入两个子节点对应的编号和区间。

巧妙的地方是，在两行递归代码的下面是给当前节点赋值的语句。因为它上面的递归回到当前这一层时，当前的节点的两个子节点已经赋好值了，所以此时可以把两个子节点的值拿来计算。

2.2 区间询问

// p是当前节点,[pl,pr]是对应区间,[l,r]为目标区间
int query(int p, int pl, int pr, int l, int r) {
        if(pl >= l && pr <= r) return tree[p];
        int mid = (pl + pr) / 2;	
        int sum = 0;
        if(mid >= l) sum += query(2*p, pl, mid, l, r);
        if(mid+1 <= r) sum += query(2*p+1, mid+1, pr, l, r);
        return sum; 
}

询问同样使用递归，并且从根节点开始向下搜索。因此以如下形式调用。

query(1, 1, n, l, r);

如果当前节点区间完全包含在目标区间内，就无需继续向下搜索，可以直接返回该节点对应的值。这正是线段树区间查询节省时间的原因。

接下来递归即可，但要判断当前区间与目标区间的位置关系，两个if语句起到了这个作用。mid是当前区间的正中间。

若 l ≤ mid，说明目标区间与 [pl, mid] 有重叠，因此需要搜索左子树，如图 2 所示。

p2
图2

若 mid < r，说明目标区间与 [mid+1, pr] 有重叠，因此需要搜索右子树，如图 3 所示。

p3
图3

2.3 单点修改

// p为当前节点，[pl,pr]为当前对应区间，目标是将第x个元素加上k
void update(int p, int pl, int pr, int x, int k) {
        if(pl == pr) {
                tree[p] += k;
                return ;
        }
        int mid = (pl + pr) / 2;
        if(x <= mid) update(p*2, pl, mid, x, k);
        if(x >= mid+1) update(p*2+1, mid+1, pr, x, k);
        tree[p] = tree[p*2] + tree[p*2+1];
}

单点修改与建树使用相同的递归结构。

2.4 区间修改与懒惰标记

若利用单点修改进行区间修改，就需要遍历区间内每个元素，时间复杂度会很高。

因此引入懒惰标记。懒惰标记就是延迟更新节点信息。对于长度为 n 的待修改区间，可以用少于 n 个线段树节点表示。修改信息只保存在这些节点上，而不立即更新其子节点；直到下次访问带标记的节点时，才进行实际下传。

在树上搜索的同时，完成懒惰标记的实现。

  1. 从根节点开始搜索。

  2. 如果当前区间为目标区间的某个子集时，这意味着区间修改对当前节点有效，那么修改当前节点的值（p表示当前节点编号）t[p] += (pr - pl + 1) * k。同时更新懒惰标记tag[p] += k。

  3. 如上文所说，直到下一次访问到标记了的节点，再进行实质性的修改

    每当访问到一个节点时，就要判断是否有标记。如果有标记的话，就把标记的信息传递到它的两个子节点上，并把当前节点的标记删去。

  4. 最后再对比区间关系，进行递归。

void update(int p, int pl, int pr, int l, int r, int k) {	
        if(pl >= l && pr <= r) { // 当前区间为目标区间的子集
                tag[p] += k;
                tree[p] += (pr - pl + 1) * k;
                return ;
        }
        int mid = (pl + pr) / 2;
        if(tag[p]) {
                tag[2*p] += tag[p];
                tag[2*p+1] += tag[p]; // 把标记传递给两个子节点
                tree[2*p] += (mid - pl + 1) * tag[p];
                tree[2*p+1] += (pr - mid) * tag[p]; // 修改两个子节点的值
                tag[p] = 0;
        }
        if(l <= mid) update(p*2, pl, mid, l, r, k);
        if(r >= mid+1) update(p*2+1, mid+1, pr, l, r, k); // 递归
        tree[p] = tree[p*2] + tree[p*2+1];
}

例如，对数组 [10, 11, 12, 13, 14] 的区间 [3, 5] 中每个元素都加上 5，如图 4 所示。

p4
图4
  1. 从根节点开始搜索，找到了[3,3]和[4,5]，分别对应第5和第3个节点。给这两个节点打上标记，并修改值。
  2. 找到之后递归函数还返回前几层，从而更新对应的节点值（如1号节点，2号节点，3号节点的值都会被更新，通过将两个子节点求和）。

修改完成后，线段树如图5所示：

p5
图5

延迟更新如何体现？例如，当前线段树中第 6、7 个节点的信息尚未更新，尽管它们属于 [3, 5] 区间；它们会在下次被访问时更新。

比如：查询[4,4]区间。

  1. 在搜索到第三个节点时（区间[4,5]），发现该节点有标记。
  2. 标记传递给两个子节点，并修改两个子节点的值。
  3. 将当前节点的标记删除。

第 6、7 个节点是叶节点，理论上无需再向下传递标记。不过通用的下传过程会对每个被访问且带标记的节点执行同样的操作，因此标记仍会传递给第 6、7 个节点，如图 6 所示。

p6
图6

若使用懒惰标记，询问的代码也需要进行修改。

int query(int p, int pl, int pr, int l, int r) {
        if(pl >= l && pr <= r) return tree[p]; // 当前区间为目标区间的子集
        int mid = (pl + pr) / 2;
        if(tag[p]) {
                tag[2*p] += tag[p];
                tag[2*p+1] += tag[p]; // 传递标记给两个子节点
                tree[2*p] += (mid - pl + 1) * tag[p];
                tree[2*p+1] += (pr - mid) * tag[p]; // 修改两个子节点的值
                tag[p] = 0;
        }
        int sum = 0;
        if(mid >= l) sum += query(2*p, pl, mid, l, r);
        if(mid+1 <= r) sum += query(2*p+1, mid+1, pr, l, r); // 递归
        return sum; 
}

3. 例题

示例 1：洛谷 P2357

一道基础模板题。区间修改和区间查询需要使用懒惰标记。

对于单点修改，可将其视为区间 [x, x] 的修改来调用。

示例 2：洛谷 P2574

对于一个长度为 n、只包含 0 和 1 的数列：修改操作将 0 变为 1、将 1 变为 0；查询操作统计目标区间内 1 的数量。

此题中，t数组表示对应区间的和，即1的个数。

修改操作的实现：t[x]表示区间内1的数量。若将该区间反转，则t[x] = len - t[x]。这应该很好理解。

tag数组的使用：若一个区间反转两次则相当于没有反转。令tag[x] = 1表示需要反转，tag[x] = 0表示不需要。每次进行修改时，令tag[x] = !tag[x]。

最后要注意，输入是字符串，需要按字符串处理。

//修改和查询的代码
void update_tag() {
  	tag[p*2] = !tag[p*2];
	tag[p*2+1] = !tag[p*2+1]; // 不同之处
	tree[2*p] = (mid - pl + 1) - tree[2*p];
	tree[2*p+1] = (pr - mid) - tree[2*p+1]; // 不同之处
	tag[p] = 0;
}
void update(int p, int pl, int pr, int l, int r) {
	if(pl >= l && pr <= r) {
		tag[p] = !tag[p]; // 不同之处
		tree[p] = (pr - pl + 1) - tree[p]; // 不同之处
		return ;
	}
	int mid = (pl + pr) / 2;
	if(tag[p]) update_tag();
	recursion1();
}

int query(int p, int pl, int pr, int l, int r) {
	if(pl >= l && pr <= r) return tree[p];
	if(tag[p]) update_tag();
	recursion2();
}

示例 3：洛谷 P1198

简单变式：将求和改为求最大值即可。

Tommy Chen
If you have the same hobbies, you can contact me.

  Subscribe to RSS Feed
Total visits to this site: times