-1.算法简介

线段树（Segment Tree），几乎是算法竞赛最常用的数据结构，适用于一个序列的区间修改、区间询问交叉进行的问题。

-2.算法讲解

我们假设一个数列1 1 4 5 1 4 4 5，现在我们需要把它从第2个数到第4个数同时加上10，然后再让你求出从第3个数到第6个数中所有书加起来的和，让你用代码写出来，你会怎么办？有人会说：“哎呀，这太简单了吧，直接暴力枚举不就行了？那如果如果我们把数据调大一些呢？问你一百万次，每次让你同时让一个十万个数的区间同时加上一个数或者求出它们的和，那你的效率不就太慢了吗？线段树就能高效率地解决这样的问题。

线 段 树

我们先构造一棵二叉树

假设节点1表示第 \(1\) 个数到第 \(8\) 个数的和，节点 \(2\) 表示第 \(1\) 个数到第 \(4\) 个数的和，节点 \(3\) 表示第 \(5\) 个数到第 \(8\) 个数的和，节点 \(4\) 表示第 \(1\) 个数到第 \(2\) 个数的和...以此类推，那每一个节点都能表示一段区间的和，是这样的：

其中[ ]里面的数表示这个节点所表示的区间，sum表示这段区间的和。

我们就把这棵二叉树称为线段树。

那如果我们需要找到一段区间的和，不就只需要找到哪些节点组合起来能够表示出这个区间，然后再把它加起来不就行了吗？修改也是一样的，只需要找到能够表示这个区间的所有叶子节点，然后加上/减去需要修改的数，然后再把它们的祖先节点都修改完，不就行了吗？这时候，有人可能就会问了：“为什么这个区间能够保证被一些节点表示出来呢？”因为每个点所表示的区间长度都是 \(2^n\)，而任何一个正整数都能被若干个 \(2^n\) 相加表示出来，所以这个区间就一定能被表示出来。

代码实现

我们使用数组来存储这棵线段树。每个节点 \(cur\) 的左孩子是 \(2cur\) ，右孩子是 \(2cur+1\) ，\(lt\) 表示这个节点表示的区间的左端点，\(rt\) 表示右端点，设 \(mid=\frac{(lt+rt)}{2}\)，那么 \(cur\) 的左孩子所表示的范围就是 \([lt,mid]\)，右孩子所表示的范围就是 \([mid+1,rt]\)。

1.建立线段树（\(\mathrm{build()}\) 函数）

我们只需一层一层地往下递归，直到叶子节点时把 \(tree[cur]\) 赋值为这个数，
否则 \(tree[cur]\) 就是它的左右两个子节点 \(tree[cur*2]\)，\(tree[cur*2+1]\) 的和。

void pushup(int cur)
{
	tree[cur] = tree[cur * 2] + tree[cur * 2 + 1];//tree[cur]是它的左右两个子节点tree[cur * 2]，tree[cur * 2 + 1]的和
	return;
}
void build(int cur, int lt, int rt)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点
{
	if(lt == rt)//如果是叶子节点（叶子节点只能表示一个点，也就是左右端点相等）
	{
		tree[cur] = a[lt];//那么叶子节点就是这个数
		return;
	}
	int mid = (lt + rt) >> 1;
	build(cur * 2, lt, mid);//递归左子树
	build(cur * 2 + 1, mid + 1, rt);//递归右子树
	pushup(cur);//给此节点赋值
	return;
}

2.设计询问函数（\(\mathrm{query()}\) 函数）

我们只需一层一层地往下递归，如果此节点覆盖的范围都在需要查询的范围内，那么就返回这个节点的值，否则就继续递归。

int query(int cur, int lt, int rt, int qx, int qy)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要查询的区间的左端点，qy表示右端点
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归，返回0
		return 0;
	if(qx <= lt && qy >= rt)//如果此节点覆盖的范围都在需要查询的范围内，返回这个节点的值
		return tree[cur];
	int mid = (lt + rt) >> 1;
	return query(cur * 2, lt, mid, qx, qy) + query(cur * 2 + 1, mid + 1, rt, qx, qy);//继续往下递归，返回左右两个子节点的和
}

3.设计修改函数（\(\mathrm{update()}\) 函数）

我们也只需一层一层地往下递归，如果是叶子节点，就加上需要修改的值，否则就就将此节点修改为它的左右两个子节点的和。

void update(int cur, int lt, int rt, int qx, int qy, int val)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要修改的区间的左端点，qy表示右端点，val表示需要修改的数
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归
		return;
	if(lt == rt)//如果是叶子节点
	{
		tree[cur] += val;//加上要修改的值
		return;//停止递归
	}
	int mid = (lt + rt) >> 1;
	update(cur * 2, lt, mid, qx, qy, val);//递归左子树
	update(cur * 2 + 1, mid + 1, rt, qx, qy, val);//递归右子树
	pushup(cur);//因为它的左右两个子节点修改了，所以此节点需要修改为左右两个子节点的和
	return;
}

现在，我们这份代码的雏形就完成了！只需要加上主函数的一些输入和调用就行了。不过为什么我不把主函数也写完呢？因为它太慢了！！！

在修改函数中，每一次都需要递归到叶子节点，如果需要修改每一个数的话，那就需要走完线段树中的每一个点，也就是 \(2^n-1\) 个点，那么修改函数的时间复杂度就变成了 \(O(2^n)\)，比暴力修改还慢，于是这份代码就需要优化。

懒 标 记（Lazy-Tag）

我们想一想，修改是干什么的呢？为什么要修改呢？因为要查询啊！修改是为查询服务的啊！你不查询，修改它有屁用啊？

我们举个例子：老师布置了一堆作业，但是不查，谁会做啊？

于是，只要它不查询，我们就把这个修改给存起来，等它查询的时候，我们再一个一个往下传，修改，不就行了吗？我们把这个操作称为懒标记。

我们使用 \(tag[cur]\) 表示 \(cur\) 这个点的懒标记，只要 \(cur\) 这个点所覆盖的范围都需要修改，我们就把它用 \(tag[cur]\) 存起来，先不修改，等到需要查询的时候，我们再修改。

查询时，我们只需要把这个点的懒标记传给它的两个子节点，让它们加上标记，下一次查询时，照样也被修改了，我们把这个操作叫作标记下传。

1.设计标记下传函数（\(\mathrm{pushdown()}\) 函数）

将 \(tag[cur]\) 打给左右子节点，且清空 \(tag[cur]\)，如果不清空的话只要重复下传就会重复加上标记，标记就错误了

void addtag(int cur, int lt, int rt, int val)//加上标记，cur表示节点编号，lt表示这个节点覆盖的区间的左端点，rt表示右端点
{
	tag[cur] += val;//此节点的标记加上它的父节点的标记
	tree[cur] += (rt - lt + 1) * val;//此节点的值加上它的父节点的值乘上它覆盖的节点数
	return;
}
void pushdown(int cur, int lt, int rt)//标记下传，cur表示节点编号，lt表示这个节点覆盖的区间的左端点，rt表示右端点
{
	if(tag[cur] == 0)//如果标记本来就是0，那么return
		return;
	int mid = (lt + rt) >> 1;
	addtag(cur * 2, lt, mid, tag[cur]);//给左孩子加上标记
	addtag(cur * 2 + 1, mid + 1, rt, tag[cur]);//给右孩子加上标记
	tag[cur] = 0;//清空标记
	return;
}

2.修改 \(\mathrm{update()}\) 函数

我们只需要把修改叶子节点的那一段删掉，只要 \(cur\) 这个点所覆盖的范围都需要修改，我们就把它用 \(tag[cur]\) 存起来，不进行修改（\(\mathrm{addtag()}\) 函数），否则就标记下传

void update(int cur, int lt, int rt, int qx, int qy, int val)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要修改的区间的左端点，qy表示右端点，val表示需要修改的数
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归
		return;
	if(qx <= lt && qy >= rt)//如果此节点覆盖的范围都在需要修改的范围内，增加标记
	{
		addtag(cur, lt, rt, val);
		return;
	}
	pushdown(cur, lt, rt);//标记下传
	int mid = (lt + rt) >> 1;
	update(cur * 2, lt, mid, qx, qy, val);//递归左子树
	update(cur * 2 + 1, mid + 1, rt, qx, qy, val);//递归右子树
	pushup(cur);//因为它的左右两个子节点修改了，所以此节点需要修改为左右两个子节点的和
	return;
}

3.修改 \(\mathrm{query()}\) 函数

我们只需要在查询左右子节点前标记下传，使得其被修改就行了

int query(int cur, int lt, int rt, int qx, int qy)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要查询的区间的左端点，qy表示右端点
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归，返回0
		return 0;
	if(qx <= lt && qy >= rt)//如果此节点覆盖的范围都在需要查询的范围内，返回这个节点的值
		return tree[cur];
	pushdown(cur, lt, rt);//标记下传
	int mid = (lt + rt) >> 1;
	return query(cur * 2, lt, mid, qx, qy) + query(cur * 2 + 1, mid + 1, rt, qx, qy);//继续往下递归，返回左右两个子节点的和
}

至此，基本的线段树我们就已经学完了，下面附上模板题的完整代码（P3372）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], tree[4 * N], tag[4 * N];
void pushup(int cur)
{
	tree[cur] = tree[cur * 2] + tree[cur * 2 + 1];//tree[cur]是它的左右两个子节点tree[cur * 2]，tree[cur * 2 + 1]的和
	return;
}
void build(int cur, int lt, int rt)//cur表示节点编号，lt表示这个节点覆盖的区间的左端点，rt表示右端点
{
	if(lt == rt)//如果是叶子节点（叶子节点只能表示一个点，也就是左右端点相等）
	{
		tree[cur] = a[lt];//那么叶子节点就是这个数
		return;
	}
	int mid = (lt + rt) >> 1;
	build(cur * 2, lt, mid);//递归左子树
	build(cur * 2 + 1, mid + 1, rt);//递归右子树
	pushup(cur);//给此节点赋值
	return;
}
void addtag(int cur, int lt, int rt, int val)//加上标记，cur表示节点编号，lt表示这个节点覆盖的区间的左端点，rt表示右端点
{
	tag[cur] += val;//此节点的标记加上它的父节点的标记
	tree[cur] += (rt - lt + 1) * val;//此节点的值加上它的父节点的值乘上它覆盖的节点数
	return;
}
void pushdown(int cur, int lt, int rt)//标记下传，cur表示节点编号，lt表示这个节点覆盖的区间的左端点，rt表示右端点
{
	if(tag[cur] == 0)//如果标记本来就是0，那么return
		return;
	int mid = (lt + rt) >> 1;
	addtag(cur * 2, lt, mid, tag[cur]);//给左孩子加上标记
	addtag(cur * 2 + 1, mid + 1, rt, tag[cur]);//给右孩子加上标记
	tag[cur] = 0;//清空标记
	return;
}
int query(int cur, int lt, int rt, int qx, int qy)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要查询的区间的左端点，qy表示右端点
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归，返回0
		return 0;
	if(qx <= lt && qy >= rt)//如果此节点覆盖的范围都在需要查询的范围内，返回这个节点的值
		return tree[cur];
	pushdown(cur, lt, rt);//标记下传
	int mid = (lt + rt) >> 1;
	return query(cur * 2, lt, mid, qx, qy) + query(cur * 2 + 1, mid + 1, rt, qx, qy);//继续往下递归，返回左右两个子节点的和
}
void update(int cur, int lt, int rt, int qx, int qy, int val)//cur表示节点编号，lt表示这个节点表示的区间的左端点，rt表示右端点，qx表示需要修改的区间的左端点，qy表示右端点，val表示需要修改的数
{
	if(qx > rt || qy < lt)//如果此节点覆盖的范围不在需要修改的范围内，停止递归
		return;
	if(qx <= lt && qy >= rt)//如果此节点覆盖的范围都在需要修改的范围内，增加标记
	{
		addtag(cur, lt, rt, val);
		return;
	}
	pushdown(cur, lt, rt);//标记下传
	int mid = (lt + rt) >> 1;
	update(cur * 2, lt, mid, qx, qy, val);//递归左子树
	update(cur * 2 + 1, mid + 1, rt, qx, qy, val);//递归右子树
	pushup(cur);//因为它的左右两个子节点修改了，所以此节点需要修改为左右两个子节点的和
	return;
}
signed main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, 1, n);
	for(int i = 1; i <= m; i++)
	{
		int opt, x, y, val;
		cin >> pt >> x >> y;
		if(opt == 1)
		{
			cin >> val;
			update(1, 1, n, x, y, val);
		}
		else
			cout << query(1, 1, n, x, y) << "\n";
	}
	return 0;
}

下转线段树习题（可能码风和习惯会有些不同，因为不是我写的，是我同学写的，请见谅！）