线段树

• 0. 概述
• 1. 递归建树
• 2. 点修改
• 3. 区间查询
• 4. 区间修改
  • 4.1. 线段树的结构
  • 4.2. 向上更新函数
  • 4.3. 向下传递懒标记的函数
• 5. 完整代码

0. 概述

• 线段树是基于分治思想的二叉树，用来维护区间信息（区间和，区间最值，区间GCD等），可以在 $O(log^n)$ 的时间内执行区间修改和区间查询（树状数组是区间查询，单点修改和单点查询、区间修改，遇到复杂问题直接无脑线段树）
• 现在看起来，线段树和归并排序非常的类似，这个数据结构比较简单

1. 递归建树

build函数：在一段区间上初始化线段树

• 二叉树的性质：父节点编号为p，那么左孩子编号为2p，右孩子编号为2p+1

const int maxn=5e5+5;
int n,w[maxn]; // w是要维护的一维数组
// l:区间的左端点
// r:区间的右端点
// sum:区间和
struct Node {
	int l,r,sum;
}t[maxn*4];

// p:根节点的编号
void build(int p,int l,int r) {
	t[p]={l,r,w[l]}; // w[l]对叶子节点才有意义,最后回溯赋值
	if(l==r)
		return; // 如果是叶子节点,返回
	int m=(l+r)>>1; // 不是叶子,则分裂,m是中点
	build(lc,l,m);
	build(rc,m+1,r);
	t[p].sum=t[lc].sum+t[rc].sum; // 更新父节点的sum值
}

• 由图可知，当有10个节点时，深度至少都为4（$10>2^3$ && $10<2^4$ ），此时编号最多能有31个（$2^5-1$）【下一层填满】，设第四层为n，那么前三层的和为n-1，倘若第五层填满（此时构成满二叉树），则根据二叉树的性质有2n个节点，此时节点一共有 $n-1+n+2n$ (最多的情况)，可以发现是最多是n的四倍，所以我们预备 $4×maxn$ 的空间。

2. 点修改

update函数：用子节点的信息更新当前节点信息

• 算法思路：从根节点开始，递归找到叶子节点，把该节点的值增加 $k$ ，找到后从下往上通过回溯的方式为父节点不断更新值

// 点修改
// p:根节点
void update(int p,int x,int k) {
	// 如果是叶子节点
	if(t[p].l==x && t[p].r==x) {
		t[p].sum+=k;
		return;
	}
	// 非叶子节点裂开,中间点为m
	int m=(t[p].l+t[p].r)>>1;
	if(x<=m)
		update(lc,x,k);
	if(x>m)
		update(rc,x,k);
	// 更新父节点的sum值
	t[p].sum=t[lc].sum+t[rc].sum;
}

3. 区间查询

query函数：区间查询

• 算法思路：拆分和拼凑，思想，例如：查询区间[4,9]可以拆分为[4,5],[6,8],[9,9]，通过合并三个结果的答案得到最终答案

• 从根节点进入，递归执行以下过程：

  1. 若查询区间[x,y]完全覆盖当前节点区间，则立即回溯，并返回该节点的sum值
  2. 若左子节点与[x,y]有重叠，则递归访问左子树
  3. 若右子节点与[x,y]有重叠，则递归访问右子树

• 举个例子，如果找[4,9]的元素和，从根节点开始，[4,9]与[1,5]有重叠，所以访问左子树，与[1,3]无重叠，所以访问[4,5]，发现[4,5]包含在[4,9]中，所以作为答案的一部分加起来；访问完了，回溯回溯，[4,9]与[6,10]有重叠，所以访问右子树，[6,10]的左子树[6,8]是[4,9]的一部分，所以作为答案的一部分加起来，继续访问右子树[9,10]与[4,9]有重叠而不是包含关系，所以访问右子树，找到[9,9]包含在[4,9]中，所以作为答案的一部分加起来，右子树[10,10]与[4,9]无重叠，不访问，全部访问完了，回溯回溯回溯，递归结束。

// 区间查询
// p:根节点编号
int query(int p,int x,int y) {
	// 如果完全覆盖了,说明你是答案的一部分,则加上
	if(x<=t[p].l && t[p].r<=y) {
		return t[p].sum;
	}
	int m=(t[p].l+t[p].r)>>1; // 如果不覆盖则分裂
	int sum=0;
	// 与左边界有重叠,则去递归查询左子树
	if(x<=m)
		sum+=query(lc,x,y);
	// 与右边界有重叠,则去递归查询右子树
	if(y>m)
		sum+=query(rc,x,y);
	return sum;
}

4. 区间修改

modify函数：区间修改

• 算法思路：例如，对区间[4,9]的每个数加上5，如果修改区间[x,y]所覆盖的每个叶子节点，时间将会是O(n)，如果我们做懒惰修改（通过一个变量来记账，并没有真正的修改这个节点中的值），先修改该区间的sum值，再打上一个“懒标记”，然后立即返回。等下次需要时，再下传“懒标记”（这个时候才是真正的赋值），这样，就可以把每次修改和查询的时间都控制到O(logⁿ)。
• 举个例子：同样还是[4,9]+5的例子，从根节点开始，分裂成[1,5]和[6,10]，未完全覆盖，继续往下，找到[4,5]，完全覆盖了，因为[4,5]的宽度为2，所以节点5的sum+=10(2×5)，打上懒标记add=5，此时对于节点5(sum=20, add=5)，找到过后回溯到2，对于1来说递归完了左子树，继续递归右子树，对于节点3，未完全覆盖，往下找到[6,8]，此时已完全覆盖，节点3的宽度为3，所以节点3的sum+=15(5×3)，打上懒标记add=5，此时对于节点3(sum=25, add=6)，回溯，递归3的右子树，向下找到完全覆盖的[9,9]，此时宽度为1，所以节点7的sum加上5，打上懒标记add=5，回溯，通过sum更新父节点的值，直至根节点，结束！

4.1. 线段树的结构

• 由于引入了懒标记add，所以结构体变为：

struct Node {
	int l; // 左子树编号 
	int r; // 右子树编号
	int sum; // 该节点所拥有的叶子节点的值之和
	int add; // 懒标记(用于区间修改中)
}t[maxn*4];

4.2. 向上更新函数

• 将t[p].sum=t[lc].sum+t[rc].sum 总结成一个函数，增强可读性，用于更新结点的sum

// 向上更新节点的sum值
void pushup(int p) {
	t[p].sum=t[lc].sum+t[rc].sum;
}

4.3. 向下传递懒标记的函数

• 向下传递懒标记是为了真正要用到这个点的时候(当然没用到这个点的时候，要求和直接用父节点的sum就行了)，能以时间复杂度O(n)的方式来为其赋值。

// 向下更新节点的sum值(通过父节点打上的懒标记)
void pushdown(int p) {
	// 如果有懒标记
	if(t[p].add) {
		// 左子树的sum值增加宽度*懒标记的值,比如左子树是[3,4](设懒标记为5),那么这个节点的值sum增加10,add为5
		// 如果后续还需要下传懒标记,再传递给[3,3]和[4,4],sum分别增加宽度为1*add(5)=5,很好理解吧?
		t[lc].sum+=t[p].add*(t[lc].r-t[lc].l+1); // right-left+1 是求宽度 
		t[rc].sum+=t[p].add*(t[rc].r-t[lc].l+1);
		t[lc].add+=t[p].add; // 懒标记增加父节点的懒标记(下传了,这个值要存起来)
		t[rc].add+=t[p].add;
		t[p].add=0; // 传完了,懒标记置为0
	}
}

5. 完整代码

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,w[maxn]; // w是要维护的一维数组

struct Node {
	int l; // 左子树编号 
	int r; // 右子树编号
	int sum; // 该节点所拥有的叶子节点的值之和
	int add; // 懒标记(用于区间修改中)
}t[maxn*4];

// 向上更新节点的sum值
void pushup(int p) {
	t[p].sum=t[lc].sum+t[rc].sum;
}

// 向下更新节点的sum值(通过父节点打上的懒标记)
void pushdown(int p) {
	// 如果有懒标记
	if(t[p].add) {
		// 左子树的sum值增加宽度*懒标记的值,比如左子树是[3,4](设懒标记为5),那么这个节点的值sum增加10,add为5
		// 如果后续还需要下传懒标记,再传递给[3,3]和[4,4],sum分别增加宽度为1*add(5)=5,很好理解吧?
		t[lc].sum+=t[p].add*(t[lc].r-t[lc].l+1); // right-left+1 是求宽度 
		t[rc].sum+=t[p].add*(t[rc].r-t[rc].l+1);
		t[lc].add+=t[p].add; // 懒标记增加父节点的懒标记(下传了,这个值要存起来)
		t[rc].add+=t[p].add;
		t[p].add=0; // 传完了,懒标记置为0
	}
//	auto &u=t[p],&l=t[lc],&r=t[rc];
//	if(u.add) {
//		l.sum+=u.add*(l.r-l.l+1),
//		r.sum+=u.add*(r.r-r.l+1),
//		l.add+=u.add,
//		r.add+=u.add,
//		u.add=0;
//	}
}

// 构造线段树
// p:根节点的编号
void build(int p,int l,int r) {
	t[p]={l,r,w[l],0}; // w[l]对叶子节点才有意义,最后回溯赋值
	if(l==r)
		return; // 如果是叶子节点,返回
	int m=(l+r)>>1; // 不是叶子,则分裂,m是中点
	build(lc,l,m);
	build(rc,m+1,r);
	// 更新父节点的sum值
	pushup(p);
}

// 点修改
// p:根节点
void update(int p,int x,int k) {
	// 如果是叶子节点
	if(t[p].l==x && t[p].r==x) {
		t[p].sum+=k;
		return;
	}
	// 非叶子节点裂开,中间点为m
	int m=(t[p].l+t[p].r)>>1;
	if(x<=m)
		update(lc,x,k);
	if(x>m)
		update(rc,x,k);
	// 更新父节点的sum值
	t[p].sum=t[lc].sum+t[rc].sum;
}

// 区间查询
// p:根节点编号
int query(int p,int x,int y) {
	// 如果完全覆盖了,说明你是答案的一部分,则加上
	if(x<=t[p].l && t[p].r<=y) {
		return t[p].sum;
	}
	int m=(t[p].l+t[p].r)>>1; // 如果不覆盖则分裂
	pushdown(p); // 下传懒标记
	int sum=0;
	// 与左边界有重叠,则去递归查询左子树
	if(x<=m)
		sum+=query(lc,x,y);
	// 与右边界有重叠,则去递归查询右子树
	if(y>m)
		sum+=query(rc,x,y);
	return sum;
}

// 区间更新
// p:根节点,x~y:区间,k:增加的值
void update(int p,int x,int y,int k) {
	// 完全覆盖才更新值
	if(x<=t[p].l && t[p].r<=y) {
		t[p].sum+=(t[p].r-t[p].l+1)*k; // 增加区间宽度*k
		t[p].add+=k; // 打上懒标记
		return;
	}
	// 如果没覆盖,则分裂,m是中间点
	int m=(t[p].l+t[p].r)>>1;
	pushdown(p); // 下传懒标记
	// 如果有重叠,去更新左子树
	if(x<=m)
		update(lc,x,y,k);
	// 如果有重叠,去更新右子树
	if(y>m)
		update(rc,x,y,k);
	pushup(p);
}

signed main() {
	int n,m; // n是数列个数,m是操作次数
	cin>>n>>m;
	// 输入要维护的一维数组
	for(int i=1;i<=n;i++) {
		cin>>w[i];
	}
	// 根据一维数组来构造线段树,意为:根节点为1,从1~n
	build(1,1,n); // 构造线段树
	int op; // 操作类型
	int l,r; // 左右区间
	int k; // 增加的值
	while(m--) {
		cin>>op;
		if(op==1) {
			cin>>l>>r>>k;
			// 区间更新
			update(1,l,r,k); // 更新
		} else if(op==2) {
			cin>>l>>r;
			// 区间求和
			cout<<query(1,l,r)<<endl;
		}
	}
	return 0;
}
/*
5个数字,5个操作
1 x y k 将[x,y]加上k
2 x y 输出[x,y]每个数的和
输入样例:
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

打赏