线段树
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在
线段树维护的信息,需要满足可加性,即能以可以接受的速度合并信息和修改信息,包括在使用懒惰标记时,标记也要满足可加性(例如取模就不满足可加性,对
线段树¶
线段树的基本结构与建树¶
线段树将每个长度不为
有个大小为
图中
通过观察不难发现,
具体要怎么用代码实现呢?
我们继续观察,有没有发现如果
思路如下:
此处给出 C++ 的代码实现,可参考注释理解:
1 2 3 4 5 6 7 8 9 10 11 | void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}
|
关于线段树的空间:如果采用堆式存储(
分析:容易知道线段树的深度是
线段树的区间查询¶
区间查询,比如求区间
以上面这张图为例,如果要查询区间
如果要查询的区间为
一般地,如果要查询的区间是
此处给出 C++ 的代码实现,可参考注释理解:
1 2 3 4 5 6 7 8 9 10 11 | int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2, sum = 0;
if (l <= m) sum += getsum(l, r, s, m, p * 2);
// 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
// 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
return sum;
}
|
线段树的区间修改与懒惰标记¶
如果要求修改区间
我们设一个数组
A 有两个儿子,一个是 B,一个是 C。
有一天 A 要建一个新房子,没钱。刚好过年嘛,有人要给 B 和 C 红包,两个红包的钱数相同都是
元,然而因为 A 是父亲所以红包肯定是先塞给 A 咯~ 1 理论上来讲 A 应该把两个红包分别给 B 和 C,但是……缺钱嘛,A 就把红包偷偷收到自己口袋里了。
A 高兴地说:「我现在有
份红包了!我又多了 2 元了!哈哈哈~」 2\times 1=2 但是 A 知道,如果他不把红包给 B 和 C,那 B 和 C 肯定会不爽然后导致家庭矛盾最后崩溃,所以 A 对儿子 B 和 C 说:「我欠你们每人
份 1 元的红包,下次有新红包给过来的时候再给你们!这里我先做下记录……嗯……我欠你们各 1 元……」 1 儿子 B、C 有点恼怒:「可是如果有同学问起我们我们收到了多少红包咋办?你把我们的红包都收了,我们还怎么装?」
父亲 A 赶忙说:「有同学问起来我就会给你们的!我欠条都写好了不会不算话的!」
这样 B、C 才放了心。
在这个故事中我们不难看出,A 就是父亲节点,B 和 C 是 A 的儿子节点,而且 B 和 C 是叶子节点,分别对应一个数组中的值(就是之前讲的数组
如图:
注:这里 D 表示当前节点的值(即所表示区间的区间和)。 为什么节点 A 的 D 是
如果这时候我们要查询区间
具体是这样操作(如图):
注:为什么是加上
由此我们可以得到,区间
区间修改(区间加上某个值):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void update(int l, int r, int c, int s, int t, int p) {
// [l,r] 为修改区间,c 为被修改的元素的变化量,[s,t] 为当前节点包含的区间,p
// 为当前节点的编号
if (l <= s && t <= r) {
d[p] += (t - s + 1) * c, b[p] += c;
return;
} // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
int m = (s + t) / 2;
if (b[p] && s != t) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
|
区间查询(区间求和):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p为当前节点的编号
if (l <= s && t <= r) return d[p];
// 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2;
if (b[p]) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
int sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p * 2);
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
return sum;
}
|
如果你是要实现区间修改为某一个值而不是加上某一个值的话,代码如下:
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 | void update(int l, int r, int c, int s, int t, int p) {
if (l <= s && t <= r) {
d[p] = (t - s + 1) * c, b[p] = c;
return;
}
int m = (s + t) / 2;
if (b[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
b[p * 2] = b[p * 2 + 1] = b[p];
b[p] = 0;
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) return d[p];
int m = (s + t) / 2;
if (b[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
b[p * 2] = b[p * 2 + 1] = b[p];
b[p] = 0;
}
int sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p * 2);
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
return sum;
}
|
一些优化¶
这里总结几个线段树的优化:
-
在叶子节点处无需下放懒惰标记,所以懒惰标记可以不下传到叶子节点。
-
下放懒惰标记可以写一个专门的函数
pushdown
,从儿子节点更新当前节点也可以写一个专门的函数maintain
(或者对称地用pushup
),降低代码编写难度。 -
标记永久化,如果确定懒惰标记不会在中途被加到溢出(即超过了该类型数据所能表示的最大范围),那么就可以将标记永久化。标记永久化可以避免下传懒惰标记,只需在进行询问时把标记的影响加到答案当中,从而降低程序常数。具体如何处理与题目特性相关,需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。
线段树基础题推荐¶
luogu P3372【模板】线段树 1¶
参考代码
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 | #include <iostream>
typedef long long LL;
LL n, a[100005], d[270000], b[270000];
void build(LL l, LL r, LL p) {
if (l == r) {
d[p] = a[l];
return;
}
LL m = (l + r) >> 1;
build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);
d[p] = d[p << 1] + d[(p << 1) | 1];
}
void update(LL l, LL r, LL c, LL s, LL t, LL p) {
if (l <= s && t <= r) {
d[p] += (t - s + 1) * c, b[p] += c;
return;
}
LL m = (s + t) >> 1;
if (b[p])
d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
b[p] = 0;
if (l <= m) update(l, r, c, s, m, p << 1);
if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
d[p] = d[p << 1] + d[(p << 1) | 1];
}
LL getsum(LL l, LL r, LL s, LL t, LL p) {
if (l <= s && t <= r) return d[p];
LL m = (s + t) >> 1;
if (b[p])
d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
b[p] = 0;
LL sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p << 1);
if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
return sum;
}
int main() {
std::ios::sync_with_stdio(0);
LL q, i1, i2, i3, i4;
std::cin >> n >> q;
for (LL i = 1; i <= n; i++) std::cin >> a[i];
build(1, n, 1);
while (q--) {
std::cin >> i1 >> i2 >> i3;
if (i1 == 2)
std::cout << getsum(i2, i3, 1, n, 1) << std::endl;
else
std::cin >> i4, update(i2, i3, i4, 1, n, 1);
}
return 0;
}
|
luogu P3373【模板】线段树 2¶
参考代码
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <cstdio>
#define ll long long
ll read() {
ll w = 1, q = 0;
char ch = ' ';
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') q = (ll)q * 10 + ch - '0', ch = getchar();
return (ll)w * q;
}
int n, m;
ll mod;
ll a[100005], sum[400005], mul[400005], laz[400005];
void up(int i) { sum[i] = (sum[(i << 1)] + sum[(i << 1) | 1]) % mod; }
void pd(int i, int s, int t) {
int l = (i << 1), r = (i << 1) | 1, mid = (s + t) >> 1;
if (mul[i] != 1) {
mul[l] *= mul[i];
mul[l] %= mod;
mul[r] *= mul[i];
mul[r] %= mod;
laz[l] *= mul[i];
laz[l] %= mod;
laz[r] *= mul[i];
laz[r] %= mod;
sum[l] *= mul[i];
sum[l] %= mod;
sum[r] *= mul[i];
sum[r] %= mod;
mul[i] = 1;
}
if (laz[i]) {
sum[l] += laz[i] * (mid - s + 1);
sum[l] %= mod;
sum[r] += laz[i] * (t - mid);
sum[r] %= mod;
laz[l] += laz[i];
laz[l] %= mod;
laz[r] += laz[i];
laz[r] %= mod;
laz[i] = 0;
}
return;
}
void build(int s, int t, int i) {
mul[i] = 1;
if (s == t) {
sum[i] = a[s];
return;
}
int mid = (s + t) >> 1;
build(s, mid, i << 1);
build(mid + 1, t, (i << 1) | 1);
up(i);
}
void chen(int l, int r, int s, int t, int i, ll z) {
int mid = (s + t) >> 1;
if (l <= s && t <= r) {
mul[i] *= z;
mul[i] %= mod;
laz[i] *= z;
laz[i] %= mod;
sum[i] *= z;
sum[i] %= mod;
return;
}
pd(i, s, t);
if (mid >= l) chen(l, r, s, mid, (i << 1), z);
if (mid + 1 <= r) chen(l, r, mid + 1, t, (i << 1) | 1, z);
up(i);
}
void add(int l, int r, int s, int t, int i, ll z) {
int mid = (s + t) >> 1;
if (l <= s && t <= r) {
sum[i] += z * (t - s + 1);
sum[i] %= mod;
laz[i] += z;
laz[i] %= mod;
return;
}
pd(i, s, t);
if (mid >= l) add(l, r, s, mid, (i << 1), z);
if (mid + 1 <= r) add(l, r, mid + 1, t, (i << 1) | 1, z);
up(i);
}
ll getans(int l, int r, int s, int t, int i) {
int mid = (s + t) >> 1;
ll tot = 0;
if (l <= s && t <= r) return sum[i];
pd(i, s, t);
if (mid >= l) tot += getans(l, r, s, mid, (i << 1));
tot %= mod;
if (mid + 1 <= r) tot += getans(l, r, mid + 1, t, (i << 1) | 1);
return tot % mod;
}
int main() {
int i, j, x, y, bh;
ll z;
n = read();
m = read();
mod = read();
for (i = 1; i <= n; i++) a[i] = read();
build(1, n, 1);
for (i = 1; i <= m; i++) {
bh = read();
if (bh == 1) {
x = read();
y = read();
z = read();
chen(x, y, 1, n, 1, z);
} else if (bh == 2) {
x = read();
y = read();
z = read();
add(x, y, 1, n, 1, z);
} else if (bh == 3) {
x = read();
y = read();
printf("%lld\n", getans(x, y, 1, n, 1));
}
}
return 0;
}
|
HihoCoder 1078 线段树的区间修改¶
参考代码
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 | #include <iostream>
int n, a[100005], d[270000], b[270000];
void build(int l, int r, int p) {
if (l == r) {
d[p] = a[l];
return;
}
int m = (l + r) >> 1;
build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);
d[p] = d[p << 1] + d[(p << 1) | 1];
}
void update(int l, int r, int c, int s, int t, int p) {
if (l <= s && t <= r) {
d[p] = (t - s + 1) * c, b[p] = c;
return;
}
int m = (s + t) >> 1;
if (b[p]) {
d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
b[p << 1] = b[(p << 1) | 1] = b[p];
b[p] = 0;
}
if (l <= m) update(l, r, c, s, m, p << 1);
if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
d[p] = d[p << 1] + d[(p << 1) | 1];
}
int getsum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) return d[p];
int m = (s + t) >> 1;
if (b[p]) {
d[p << 1] = b[p] * (m - s + 1), d[(p << 1) | 1] = b[p] * (t - m);
b[p << 1] = b[(p << 1) | 1] = b[p];
b[p] = 0;
}
int sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p << 1);
if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
return sum;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin >> n;
for (int i = 1; i <= n; i++) std::cin >> a[i];
build(1, n, 1);
int q, i1, i2, i3, i4;
std::cin >> q;
while (q--) {
std::cin >> i1 >> i2 >> i3;
if (i1 == 0)
std::cout << getsum(i2, i3, 1, n, 1) << endl;
else
std::cin >> i4, update(i2, i3, i4, 1, n, 1);
}
return 0;
}
|
2018 Multi-University Training Contest 5 Problem G. Glad You Came¶
维护一下每个区间的永久标记就可以了,最后在线段树上跑一边 dfs 统计结果即可。注意打标记的时候加个剪枝优化,否则会 T。
拓展 - 猫树¶
众所周知线段树可以支持高速查询某一段区间的信息和,比如区间最大子段和,区间和,区间矩阵的连乘积等等。
但是有一个问题在于普通线段树的区间询问在某些毒瘤的眼里可能还是有些慢了。
简单来说就是线段树建树的时候需要做
而所谓 "猫树" 就是一种不支持修改,仅仅支持快速区间询问的一种静态线段树。
构造一棵这样的静态线段树需要
在处理线性基这样特殊的信息的时候甚至可以将复杂度降至
原理¶
在查询
1.
显然,因为它既是
2.
由于
因此
有了这两个性质,我们就可以将询问的复杂度降至
实现¶
具体来讲我们建树的时候对于线段树树上的一个节点,设它代表的区间为
不同于传统线段树在这个节点里只保留
这样的话建树的复杂度为
下面是最关键的询问了~
如果我们询问的区间是
根据刚才的两个性质,
这意味这一个非常关键的事实是我们可以使用
而这个过程仅仅需要
不过我们好像忽略了点什么?
似乎求 lca 的复杂度似乎还不是
堆式建树¶
具体来将我们将这个序列补成 2 的整次幂,然后建线段树。
此时我们发现线段树上两个节点的 lca 编号,就是两个节点二进制编号的 lcp。
稍作思考即可发现发现在 lcp(x,y)=x>>log[x^y]
。
所以我们预处理一个 log
数组即可轻松完成求 lca 的工作。
这样我们就完成了一个猫树。
由于建树的时候涉及到求前缀和和求后缀和,所以对于线性基这种虽然合并是
参考¶
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:Marcythm, Ir1d, Ycrpro, Xeonacid, konnyakuxzy, CJSoft, HeRaNO, ethan-enhe, ChungZH, Chrogeek, hsfzLZH1, billchenchina, orzAtalod
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用