区间求和问题，需要使用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倍。