Segment Tree 线段树笔记

Allen2010 Lv2
  2025-03-22 2025-03-22 Created   2025-04-06 20:02:51 2025-04-06 20:02:51 Updated      1.8k Words  8 Mins  

算法描述

线段树常用于解决区间修改查询问题，包括但不限于最大值、最小值和求和。线段树最大的难点，就是你不知道它将用来解决怎样的问题。

定义

线段树就是一棵普普通通的树，它的大部分节点都有两个子节点，但并不是一棵满二叉树，也不是完全二叉树。这一点你在学习后面的文章后就会明白了。
线段树上每一个节点都代表着一段区间，而每个子结点代表的区间长度都是其父节点的一半。若长度是奇数则会有些许偏差。而节点的值则是这个区间的需求。

应用

线段树可以解决大部分的区间问题，只要你能想清楚怎么分治，基本上就是线段树没得跑。哪怕这个区间的需求是连续的。
通常来说，线段树的操作分为以下几种：

  • 建树：输入数组并建立对应需求的线段树
  • 单点修改：将 位置的元素改成
  • 区间修改：将 到 位置的所用元素改成或增加
  • 区间查询：查询 到 区间内的最大/最小/和/其他需求

算法实现

线段树用数组实现。注意数组大小要开到 。左右子树的编号分别是 和 。

1
2
ll lc(ll p){return p << 1;}
ll rc(ll p){return p << 1 | 1;}

初始化

从根节点开始，不断的分割区间直到该区间只剩单个数，然后开始向上汇总。传入两个变量 l 和 r， 表示当前节点表示的线段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void pushUp(ll p){
	sum[p] = sum[lc(p)] + sum[rc(p)];
}

void build(ll p, ll l, ll r){
	if(l == r){
		sum[p] = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	pushUp(p); 
}

区间查询

从根节点开始，如果当前的线段不被查询的区间完全包含就一直分两段尝试，直到它被完全包含了，返回该线段的值然后继续递归其他的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll Query(ll p, ll l, ll r, ll ql, ll qr){
	if(ql <= l && qr >= r){
		return sum[p];
	}
	pushDown(p, l, r);
	ll mid = (l + r) >> 1, ans = 0;
	if(ql <= mid){
		ans += Query(lc(p), l, mid, ql, qr);
	}
	if(qr > mid){
		ans += Query(rc(p), mid + 1, r, ql, qr);
	}
	return ans;
}

区间修改

如果每次修改都从上到下全改一遍，复杂度得 ，太浪费时间了，完全体现不出线段树的优势所在。因此引入懒标记（Lazy Tag）。和查询一样，当线段被区间完全覆盖时，对应的节点自己更新，但它的孩子们不更新。这时给他安上一个懒标记，表示它的子节点需要更新的大小。当区间没有完全覆盖，需要拆分的时候，将当前变量的标记拆掉，传给子节点，这样才不会错算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Update(ll p, ll l, ll r, ll ql, ll qr, ll d){
	if(ql <= l && qr >= r){
		sum[p] += d * (r - l + 1);
		tag[p] += d;
		return;
	}
	pushDown(p, l, r);
	ll mid = (l + r) >> 1;
	if(ql <= mid){
		Update(lc(p), l, mid, ql, qr, d);
	}
	if(qr > mid){
		Update(rc(p), mid + 1, r, ql, qr, d);
	}
	pushUp(p);
}

例题

例题：Luogu P3372

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
ll segt[4 * MAXN], tag[4 * MAXN], a[MAXN];
ll lc(ll p){return p << 1;}
ll rc(ll p){return p << 1 | 1;}
void pushUp(ll p){
    segt[p] = min(segt[lc(p)], segt[rc(p)]);
}
void build(ll p, ll l, ll r){
    if(l == r){
        segt[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    pushUp(p);
}
void moveTag(ll p, ll k){
    tag[p] += k;
    segt[p] += k;
}
void pushDown(ll p){
    moveTag(lc(p), tag[p]);
    moveTag(rc(p), tag[p]);
    tag[p] = 0;
}
void Update(ll p, ll l, ll r, ll ql, ll qr){
    if(ql <= l && qr >= r){
        moveTag(p, 1);
        return;
    }
    pushDown(p);
    ll mid = (l + r) >> 1;
    if(ql <= mid)Update(lc(p), l, mid, ql, qr);
    if(qr > mid)Update(rc(p), mid + 1, r, ql, qr);
    pushUp(p);
}
ll Query(ll p, ll l, ll r, ll ql, ll qr){
    if(ql <= l && qr >= r){
        return segt[p];
    }
    pushDown(p);
    ll mid = (l + r) >> 1, ans = 2147483647;
    if(ql <= mid)ans = min(ans, Query(lc(p), l, mid, ql, qr));
    if(qr > mid)ans = min(ans, Query(rc(p), mid + 1, r, ql, qr));
    return ans;
}
int main(){
    ll n, m;
    cin >> n >> m;
    for(ll i = 1; i <= n; i ++){
        cin >> a[i];
    }
    build(1, 1, n);
    while(m --){
        ll opt, l, r;
        cin >> opt >> l >> r;
        if(opt == 1){
            Update(1, 1, n, l, r);
        }else{
            cout << Query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

变种

区间和并

在遇到有区间连续的需求时，我们发现传统线段树并不适用，因为分段时无法控制答案的范围，在向上整理回父节点时可能会遇到答案的中间部分没有连接但却错误转移的情况。
我们可以定义额外的变量存于线段树的数组，分别表示了以区间最左边和最右边起始的答案，这样就只需要思考如何 pushUp 转移了。

例题

例题：区间最大连续子序列和
输入一个长度为 的数组 ，数组的元素均为整数且满足 。对该数组可以发出 条指令。指令共有 种：

  • 1 x v，该指令将 的值修改为
  • 2 l r，该指令查询区间 到 的最大连续子序列和，即区间所有可能的连续子序列中求和的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const ll MAXN = 400005, fINF = LONG_LONG_MIN;
struct Node{
    ll sum = 0, lans = fINF, rans = fINF, ans = fINF;
}segt[4 * MAXN];
ll a[MAXN];
ll lc(ll p){return p << 1;}
ll rc(ll p){return p << 1 | 1;}
void pushUp(ll p){
    segt[p].sum = segt[lc(p)].sum + segt[rc(p)].sum;
    segt[p].lans = max({segt[lc(p)].sum + segt[rc(p)].lans, segt[lc(p)].lans});
    segt[p].rans = max({segt[rc(p)].sum + segt[lc(p)].rans, segt[rc(p)].rans});
    segt[p].ans = max({segt[lc(p)].rans + segt[rc(p)].lans, segt[lc(p)].ans, segt[rc(p)].ans});
}
void build(ll p, ll l, ll r){
    if(l == r){
        segt[p].ans = segt[p].lans = segt[p].rans = segt[p].sum = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(lc(p), l, mid);
    build(rc(p), mid + 1, r);
    pushUp(p);
}
void Update(ll p, ll l, ll r, ll x, ll v){
    if(l == r){
        segt[p].sum = segt[p].ans = segt[p].lans = segt[p].rans = v;
        return;
    }
    ll mid = (l + r) >> 1;
    if(x <= mid)Update(lc(p), l, mid, x, v);
    else if(x > mid)Update(rc(p), mid + 1, r, x, v);
    pushUp(p);
}
Node Query(ll p, ll l, ll r, ll ql, ll qr){
    if(ql <= l && qr >= r){
        return segt[p];
    }
    ll mid = (l + r) >> 1;
    if(ql <= mid && qr > mid){
        Node ans, qla = Query(lc(p), l, mid, ql, qr), qra = Query(rc(p), mid + 1, r, ql, qr);
        ans.sum = qla.sum + qra.sum;
        ans.ans = max({ans.ans, qla.ans, qra.ans, qla.rans + qra.lans});
        ans.lans = max({ans.lans, qla.lans, qla.sum + qra.lans});
        ans.rans = max({ans.rans, qra.rans, qra.sum + qla.rans});
        return ans;
    }else if(ql <= mid){
        return Query(lc(p), l, mid, ql, qr);
    }else{
        return Query(rc(p), mid + 1, r, ql, qr);
    }
}
int main(){
    ll n, m;
    cin >> n >> m;
    for(ll i = 1; i <= n; i ++){
        cin >> a[i];
    }
    build(1, 1, n);
    while(m --){
        ll opt, l, r;
        cin >> opt >> l >> r;
        if(opt == 1){
            Update(1, 1, n, l, r);
        }else{
            cout << Query(1, 1, n, l, r).ans << "\n";
        }
    }
    return 0;
}

总结

极为常用，需要会用、会推、会写且达到熟练的地步。复杂度 ，已经很快了。

  • Title: Segment Tree 线段树笔记
  • Author: Allen2010
  • Created at : 2025-03-22 00:00:00
  • Updated at : 2025-04-06 20:02:51
  • Link: https://allen2010.github.io/2025/03/22/Segment Tree/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
Segment Tree 线段树笔记
  1. 算法描述
    1. 定义
    2. 应用
  2. 算法实现
    1. 初始化
    2. 区间查询
    3. 区间修改
    4. 例题
  3. 变种
    1. 区间和并
    2. 例题
  4. 总结