区间求和问题,需要使用RMQ算法。常见的RMQ算法有ST算法和线段树。ST算法适用于离线操作,本题中还需要对某一下标范围内的数字都加上一个给定的值,所以使用线段树。
线段树的基本思想是分治,每一个节点存储的是一段区间的结果。(如图1,展示的是1~8区间)一颗线段树具有插入、修改、查询三个基本功能。
图1
线段树中的节点在内存中都是连续的,那如何找到一个节点的子节点呢?以图1中[1,4]节点为例,该节点编号为4,该节点的子节点编号为8和9。我们可以发现,左子节点的编号是父节点编号*2。事实上,对于[a,b]编号为n的节点,它的左子节点[a,(a+b)/2]编号为2*n,右子节点[(a+b)/2+1,b]编号为2*n+1。
有了对节点的初步认识后,我们就可以建树了。在本题中,结构体内存放两个数据,value和lazy。值得注意的是,创建结构体数组时,结构体个数为4*MAXN(至于为什么是4,后面会讲到)
void build(int l, int r, int p)
{
if (l == r)当节点的左右范围相等时,我们就可以认为它到根部了
{
scanf("%lld", &tree[p].v);
return;
}
int mid = (l + r) / 2;
build(l, mid, p * 2);
build(mid + 1, r, p * 2 + 1);
tree[p].v = tree[p * 2].v + tree[p * 2 + 1].v;//父节点的值=左节点+右节点
}
接下来就是查询了,图2演示了对于区间[4,7]的查询过程。蓝色节点是被查询的节点。
整个查询过程,就是判断左右子节点是否在查询范围内,如果在,就进入,如果不在,就停止。如果该节点完全包含在被查询区域内,就直接返回结果,不需要进入子节点(线段树省时的原因就在这里)如果只有其中一个子节点在查询范围内,就只进入该节点。(例如5号节点[3,4],只进入了右节点)
int query(int l, int r,int x, int y,int p)
{
if (l <= x && y <= r)return tree[p];//如果该节点完全包含在被查询区域内,就返回结果。
int mid = (x + y) / 2;
if (r <= mid)return query(l, r, x, mid, p * 2);//只进入左节点
if (mid<l)return query(l, r, mid + 1, y, p * 2 + 1);//只进入右节点
return max(query(l, mid, x, mid, p * 2), query(mid + 1,r, mid + 1, y, p * 2 + 1));//左右两个节点都进入
}
接下来就是重点,如果去修改节点的值。它的复杂之处在于,上层节点的结果来自于根部节点,我们不能只去修改根部节点而不去更新上层节点,也不能只更新上层节点而不修改根部节点。但是全部更新一遍太麻烦了,又耗时,所以我们引入了lazy tag。
Lazy tag的原理是,我们在对一段区间做操作时,可以先不更新子节点,而是先把这个结果存在父节点lazy变量里,等到查询到这个节点的时候,再去更新子节点的值。这样可以节省很多不必要的更新操作,因为可能不是所有被修改的区间都被查询到,而且全部更新一遍非常耗时,还可以实现缓存(多次对一段区间做操作可以合并为一次更新)
例如对区间[2,7]都加上5,3~6的根节点没有被更新,只更新了[3,4][5,6]两个节点。(图3)
void update(int l, int r, int x, int y, int p, int num)
{
if (l <= x && y <= r)//当前区间完全包含在被更新区间时就不再向子节点更新
{
tree[p].v += (y - x + 1) * num;
tree[p].lazy += num;
return;
}
if (tree[p].lazy)push_down(x, y, p);//如果当前节点lazy值不为0,就说明已经有值缓存在lazy中了,子节点必须先更新
int mid = (x + y) / 2;
if (l <= mid)update(l, r, x, mid, p * 2, num);
if (mid < r)update(l, r, mid + 1, y, p * 2 + 1, num);
tree[p].v = tree[p * 2].v + tree[p * 2 + 1].v;
}
在查询的时候,和前文提到的方式类似,唯一的区别在于当该节点lazy值不为0时,就要先把lazy的值加到两个子节点上再进行查询。
ll query(int l, int r, int x, int y, int p)
{
if (l <= x && y <= r)return tree[p].v; //当前区间完全包含在被查询区间时就直接返回结果
if (tree[p].lazy)push_down(x, y, p);// 如果当前节点lazy值不为0,就说明已经有值缓存在lazy中了,子节点必须先更新
int mid = (x + y) / 2;
ll ans = 0;
if (l <= mid)ans += query(l, r, x, mid, p * 2);
if (mid < r)ans += query(l, r, mid + 1, y, p * 2 + 1);
return ans;
}
建树,查询,修改到此就结束了,接下来回到之前的问题,为什么开数组/结构体的时候要乘4倍呢?
可以发现,第3层已经出现了区间为1的节点了([3,3],[4,4],[5,5]),但是还有两个区间为的节点在第4层。那第4层其它的节点可以省略吗?答案是不能。
图5中[3,3]没有子节点,但是这两个节点必须留着,否则会影响到[4,5]的子节点。
相同层数的线段树使用的节点数都是一样的,都是$2^{n+1}-1$个。例如[1,5]和[1,6]都是4层,需要15个节点。
[1,[$2^{n-1}+1$,$2^{n}$]]的线段树层数相同,使用的节点数相同,均为$2^{n+1}-1$个。
所以可以发现,[1,$2^{n-1}+1$]剩下的节点数最多,使用的节点数为自身数量的$\frac{2^{n+1}-1}{2^{n-1}+1}$约等于4倍。