--在这篇博客中，你能找到什么--

        ·原题呈现及题意简析

        ·什么是线段树

        ·两个前置问题

        ·如何在数组中获得一个节点的左孩子和右孩子

        ·线段树开辟多大的空间比较合适

        ·线段树的代码实现

        ·建树函数build

        ·区间修改函数update

        ·查询函数query

        ·本题完整代码

        ·lazy标志优化

        ·标志下传函数down

        ·lazy优化后的完整代码

        ·线段树与差分数组的比较

首先，让我们来看一下今天的题目吧：

[原题]

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 kk。
2. 求出某区间每一个数的和。

[输入格式]

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 [x, y] 内每个数加上 k。
2. 2 x y：输出区间 [x, y] 内每个数的和。

[输出格式]

输出包含若干行整数，即为所有操作 2 的结果。

[输入样例]

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

[输出样例]

11
8
20

[说明/提示]

[样例解释]

[解题思路]

给出一组长度为n的数列arr，接下来对arr进行m次的区间值的增加或区间和的查询，要求输出每一步查询的结果。

很明显，这是一个区间修改的问题，同时需要多次查询，在这里，我们将采用线段树的方法。

那么，什么是线段树呢？

线段树是以二叉树为基础的树形数据结构，通过将一个区间不断二分为小的子区间，来达成快速修改和查询区间值的目的。

接下来，我们将测试用例的数据搭建一棵线段树：

可以看出，从根点开始，我们每次将整个区间二分为两个子区间作为该节点的子节点，最后的叶节点即是arr中所给每个单一位置的初始值。另外，由于本题要求区间值的和，因此我们通过每个节点来存储对应区间的总和。此外，线段树还可以用于解决求区间最值等问题。

树建完后，假如我们需要查询区间[1,3]中的和，我们只需要进行一层递归，如下图：

当然，我们也可以查询[1,4]中的和，这个过程如下图：

也许从这个过程中我们很难体会到线段树相比于直接遍历的优越性，但是不难想象，当数据范围很大，查询次数很多时，利用线段树进行查询操作可以减少大量不必要的遍历，从而减少时间复杂度。

另外，我们还可以使用对线段树进行区间修改，现在，我们要将[2,4]中的值全都增加1，这个过程如下图：

值得注意的是，在这个过程中，我们不但需要对每一个叶节点进行改值，同时也要对相关的每一个父节点进行维护。

了解了什么是线段树，那么我们该如何用代码去实现它呢？在这之前，我们需要先解决两个问题。

第一，我们如何获得一个节点的左节点和右节点？

由二叉树的性质可知，假定根节点位置为1，若父节点在数组中的位置为pos，则左节点的位置为2*pos，右节点的位置为2*pos+1。因此，我们可以通过两个内联函数来快速获得左右节点的位置，代码如下（此处通过按位运算来提高运行效率）：

inline ll leftson(ll fa)
{
	return fa << 1;
}

inline ll rightson(ll fa)
{
	return fa << 1 | 1;
}

其中，由于pos左移一位后末位一定为0，因此直接|1即可实现+1的操作。

第二，我们需要开多大的空间来存储这个线段树？

首先，最容易判断的情况就是一个满二叉树。

 

现在，我们不妨为它的一个（或一些）节点连上子节点。

不难发现，当连上一个子节点，那么叶节点的总数不会改变；当连上两个子节点，叶节点总数会多出一个。也就是说，在连接之后，倒数第二层的节点个数N≤叶节点总数n恒成立。

由于线段树的所有叶节点代表的正是arr中每个单一位置的值，因此，线段树恰能用形似上图的结构来表示。

我们暂时去掉最后一层，因为剩下的树结构是一棵满二叉树，因此节点总数为2N-1。

接下来，我们如果把最后一层开满，那么最后一层的节点个数为2N。

综合以上几点，我们可知整棵树的节点总数 ≤ 4N-1 ≤ 4n-1，习惯上，我们认为线段树数组开满4n的大小即可。

接下来，让我们来学习关键代码的书写吧。

在使用线段树之前，我们需要建树。而树的建立，势必需要进行递归。

我们设计Build函数，传入区间的左右值及当前对应节点在数组中的位置，并不断二分区间来进行递归。

递归的关键就在于终止条件的设置和函数的自我调用。显然，这里的终止条件就是区间左右端相等，即表示一个arr中的值。另外，我们通过左右端的平均值mid对区间进行二分建树。

当然，每个父节点是两个子节点之和，因此我们需要进行回溯操作来更新父节点的值。

这一段代码如下：

//根据arr数组创建线段树|传入参数：区间最左端left，区间最右端right，树节点位置pos
void build(ll left, ll right, ll pos = 1)
{
	//区间仅有一个值时（叶节点）更新并return
	if (left == right)
	{
		sum[pos] = arr[left];
		return;
	}

	//取区间中点并二分建树
	ll mid = (left + right) >> 1;
	build(left, mid, leftson(pos));
	build(mid + 1, right, rightson(pos));

	//回溯更新父节点的和
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)];
}

接下来是进行区间修改，我们同样用一个update函数来实现。这里传入参数为需要修改的区间左右端left和right，当前正在搜索的区间左右端current_left和current_right，为每个节点增加的值val，以及当前节点在数组中的位置pos。

同样地，当搜索区间的左右端相等时，我们为当前节点的值加上val并return。否则，我们将二分搜索区间，直到搜索区间包含于修改区间。

当然，因为涉及二分，这里同样取搜索区间左右端的均值mid，并作出如下判断：

（1）如果mid≥修改区间右端right，则说明mid右侧的区间没有需要修改的值，则只需对左半区间进行下一步递归。
（2）如果mid<修改区间左端left，则说明mid左侧的区间没有需要修改的值，则只需对右半区间进行下一步递归。
（3）若（1）（2）都不满足，则需要对两边的区间都进行递归搜索。

叶节点的值改变了，那么其祖宗节点一定都改变了，因此我们需要进行回溯来维护所有祖宗节点的值。

这一段代码如下：

//进行区间值修改|传入参数：修改区间的最左端left，修改区间的最右端right，当前搜索区间左端current_left，当前搜索区间的右端current_right，树节点的位置pos
void update(ll left, ll right, ll current_left, ll current_right, ll val, ll pos = 1)
{
	//递归至叶节点时更新值并返回
	if (current_left == current_right)
	{
		sum[pos] += val;
		return;
	}

	//否则二分区间，搜索对应区间的节点
	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		update(left, right, current_left, mid, val, leftson(pos));
	else if (left > mid)
		update(left, right, mid + 1, current_right, val, rightson(pos));
	else
	{
		update(left, right, current_left, mid, val, leftson(pos));
		update(left, right, mid + 1, current_right, val, rightson(pos));
	}

	//回溯更新父节点的和
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)];
}

用同样的方式，我们可以完成查询函数query的书写。

不同的是，在查询区间的和时，假如搜索区间完全包含于查询区间，则可以直接返回该节点的值。当然，由于查询过程不涉及节点值的改变，自然不需要回溯操作。

这一段代码如下：

//进行区间和查询|传入参数：查询区间最左端left，查询区间最右端right，当前搜索区间左端current_left，当前搜索区间的右端current_right，树节点的位置pos
ll query(ll left, ll right, ll current_left, ll current_right, ll pos = 1)
{
	//若搜索区间包含于查询区间，则直接返回值
	if (left <= current_left && right >= current_right)
	{
		return sum[pos];
	}

	//否则二分区间，搜索对应的子区间或节点
	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		return query(left, right, current_left, mid, leftson(pos));
	else if (left > mid)
		return query(left, right, mid + 1, current_right, rightson(pos));
	else
		return query(left, mid, current_left, mid, leftson(pos)) + query(mid + 1, right, mid + 1, current_right, rightson(pos));
}

让我们来看一下这道题的完整代码：

#include
#include
typedef long long ll;
using namespace std;

vector arr;
vector sum;

//获取左节点
inline ll leftson(ll fa)
{
	return fa << 1;
}

//获取右节点
inline ll rightson(ll fa)
{
	return fa << 1 | 1;
}

//根据arr数组创建线段树|传入参数：区间最左端left，区间最右端right，树节点位置pos
void build(ll left, ll right, ll pos = 1)
{
	//区间仅有一个值时（叶节点）更新并return
	if (left == right)
	{
		sum[pos] = arr[left];
		return;
	}

	//取区间中点并二分建树
	ll mid = (left + right) >> 1;
	build(left, mid, leftson(pos));
	build(mid + 1, right, rightson(pos));

	//回溯更新父节点的和
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)];
}

//进行区间值修改|传入参数：修改区间的最左端left，修改区间的最右端right，当前搜索区间左端current_left，当前搜索区间的右端current_right，树节点的位置pos
void update(ll left, ll right, ll current_left, ll current_right, ll val, ll pos = 1)
{
	//递归至叶节点时更新值并返回
	if (current_left == current_right)
	{
		sum[pos] += val;
		return;
	}

	//否则二分区间，搜索对应区间的节点
	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		update(left, right, current_left, mid, val, leftson(pos));
	else if (left > mid)
		update(left, right, mid + 1, current_right, val, rightson(pos));
	else
	{
		update(left, right, current_left, mid, val, leftson(pos));
		update(left, right, mid + 1, current_right, val, rightson(pos));
	}

	//回溯更新父节点的和
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)];
}

//进行区间和查询|传入参数：查询区间最左端left，查询区间最右端right，当前搜索区间左端current_left，当前搜索区间的右端current_right，树节点的位置pos
ll query(ll left, ll right, ll current_left, ll current_right, ll pos = 1)
{
	//若搜索区间包含于查询区间，则直接返回值
	if (left <= current_left && right >= current_right)
	{
		return sum[pos];
	}

	//否则二分区间，搜索对应的子区间或节点
	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		return query(left, right, current_left, mid, leftson(pos));
	else if (left > mid)
		return query(left, right, mid + 1, current_right, rightson(pos));
	else
		return query(left, mid, current_left, mid, leftson(pos)) + query(mid + 1, right, mid + 1, current_right, rightson(pos));
}

int main()
{
	//cin,cout优化
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	//读取数据及数组初始化
	int n, m;
	cin >> n >> m;
	arr = vector(n + 2, 0);//存放每个位置初始值
	sum = vector((n << 2) + 2, 0);//线段树（各子区间的和）
	vector ans;//存放查询结果
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}

	//从1~n创建树
	build(1, n);

	//进行区间修改或区间和查询
	while (m--)
	{
		ll t;
		cin >> t;
		switch (t)
		{
		case 1:
		{
			ll x, y, k;
			cin >> x >> y >> k;
			update(x, y, 1, n, k);
			break;
		}
		case 2:
		{
			ll x, y;
			cin >> x >> y;
			ans.push_back(query(x, y, 1, n));
			break;
		}
		}
	}

	//输出结果
	if (ans.size())
		cout << ans[0];
	for (int i = 1; i < ans.size(); i++)
	{
		cout << 'n' << ans[i];
	}
	return 0;
}

以上仅是线段树的简单实现，但并不能把树的优势完全发挥出来。接下来，我们将用lazy标志来对update过程进行优化。

不难发现，上述过程中，我们在每一次区间修改时，仍然需要遍历每一个节点来进行改值，但是很多进行改值的节点我们并不需要进行查询，因此，在这个过程中我们进行了许多无用功。

lazy标志的作用就在于，当搜索区间包含于修改区间时，我们就给当前节点打上lazy标志后直接返回。若下一次需要对其子节点进行操作（区间修改或查询）时，再将lazy标志中的值还给它的子节点。这样，我们就可以减少不必要的递归操作了。

当然，这个过程中，我们给父节点打上lazy标志的同时，需要更新父节点的值，由于子节点的值没有更新，因此回溯的计算公式就变为了父节点的值=两个子节点的值之和+lazy标志的值*区间长度（因为区间内每个叶节点都需要加上lazy标志的值）。

另外，我们需要设计一个lazy标志下传函数down，其主要功能为：（1）更新子节点的值 （2）将父节点的lazy标志传给子节点 （3）清空父节点的lazy标志

相关代码如下：

//更新下一层的值并下传lazy标志
void down(ll pos, ll current_left, ll current_right)
{
	//若该位置没有lazy标志或处于叶节点，直接返回
	if (!lazy[pos] || current_left == current_right) return;

	//更新两个子节点的值：加上lazy的值*区间长度
	ll ls = leftson(pos), rs = rightson(pos);
	ll mid = (current_left + current_right) >> 1;
	sum[ls] += lazy[pos] * (mid - current_left + 1);
	sum[rs] += lazy[pos] * (current_right - mid);

	//下传lazy标志并清空该位置的lazy标志
	lazy[ls] += lazy[pos];
	lazy[rs] += lazy[pos];
	lazy[pos] = 0;
}

如果说lazy标志相当于将子节点值的增量全部打包起来，那么down函数就相当于对lazy标志的解包操作，而且这个解包操作每次只会对下一层的子节点进行解包，并不会对所有子节点完全解包。

这样逐层解包，可以大大减少不必要的时间损耗。

接下来，就让我们看一下加上lazy标志优化后的完整的代码吧：

#include
#include
typedef long long ll;
using namespace std;

vector arr;
vector sum;
vector lazy;

inline ll leftson(ll fa)
{
	return fa << 1;
}

inline ll rightson(ll fa)
{
	return fa << 1 | 1;
}

void build(ll left, ll right, ll pos = 1)
{
	if (left == right)
	{
		sum[pos] = arr[left];
		return;
	}
	build(left, (left + right) >> 1, leftson(pos));
	build(((left + right) >> 1) + 1, right, rightson(pos));
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)];
}

//更新下一层的值并下传lazy标志
void down(ll pos, ll current_left, ll current_right)
{
	//若该位置没有lazy标志或处于叶节点，直接返回
	if (!lazy[pos] || current_left == current_right) return;

	//更新两个子节点的值：加上lazy的值*区间长度
	ll ls = leftson(pos), rs = rightson(pos);
	ll mid = (current_left + current_right) >> 1;
	sum[ls] += lazy[pos] * (mid - current_left + 1);
	sum[rs] += lazy[pos] * (current_right - mid);

	//下传lazy标志并清空该位置的lazy标志
	lazy[ls] += lazy[pos];
	lazy[rs] += lazy[pos];
	lazy[pos] = 0;
}

void update(ll left, ll right, ll current_left, ll current_right, ll val, ll pos = 1)
{
	//若当前搜索区间包含于修改区间，同步修改sum和lazy的值并返回
	if (left <= current_left && right >= current_right)
	{
		sum[pos] += val * (current_right - current_left + 1);//val*区间长度
        //注：由于本题中lazy标志是可以叠加的，因此使用+=而不是=
		lazy[pos] += val;
		return;
	}

	//否则，当前节点可能已有lazy标志，将标志下传
	down(pos, current_left, current_right);
	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		update(left, right, current_left, mid, val, leftson(pos));
	else if (left > mid)
		update(left, right, mid + 1, current_right, val, rightson(pos));
	else
	{
		update(left, right, current_left, mid, val, leftson(pos));
		update(left, right, mid + 1, current_right, val, rightson(pos));
	}

	//回溯（同时加上lazy标志*区间长度的值）
	sum[pos] = sum[leftson(pos)] + sum[rightson(pos)] + lazy[pos] * (current_right - current_left + 1);
}

ll query(ll left, ll right, ll current_left, ll current_right, ll pos = 1)
{
	if (left <= current_left && right >= current_right)
	{
		return sum[pos];
	}

	//若不能直接返回区间值，则需下传lazy标志
	down(pos, current_left, current_right);

	ll mid = (current_left + current_right) >> 1;
	if (right <= mid)
		return query(left, right, current_left, mid, leftson(pos));
	else if (left > mid)
		return query(left, right, mid + 1, current_right, rightson(pos));
	else
		return query(left, right, current_left, mid, leftson(pos)) + query(left, right, mid + 1, current_right, rightson(pos));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	arr = vector(n + 2, 0);
	sum = vector((n << 2) + 2, 0);
	lazy = vector((n << 2) + 2, 0);//存储lazy标志
	vector ans;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}

	build(1, n, 1);

	while (m--)
	{
		int t;
		cin >> t;
		switch (t)
		{
		case 1:
		{
			ll x, y, k;
			cin >> x >> y >> k;
			update(x, y, 1, n, k);
			break;
		}
		case 2:
		{
			ll x, y;
			cin >> x >> y;
			ans.push_back(query(x, y, 1, n));
			break;
		}
		}
	}

	if (ans.size())
		cout << ans[0];
	for (int i = 1; i < ans.size(); i++)
	{
		cout << 'n' << ans[i];
	}
	return 0;
}

同样能解决区间叠加问题，那么线段树和差分数组有什么不同之处呢？

显然，两者都能进行区间修改和区间查询，但优化方向存在差异。

对于差分数组，区间修改的时间复杂度为o(1)，而区间查询的时间复杂度为o(n)；而对于线段树，区间修改和查询的时间复杂度都为o(logn)。

因此，差分数组适用于多次区间修改，少量次查询的情况，同时适用于数据范围为1e7以内的问题；而线段树则适用于多次区间修改，多次查询的情况，且数据范围通常小于1e5。