线段树学习笔记（更新中）

本文章开始写作于2024年3月10日22：48，这也是我第一次没有参考板子，独立写出一个线段树的时刻（虽然只是板子题并且debug的时候还是参考了一下）

写这个主要是为了我自己以后复习起来方便，毕竟这玩意还是极其容易写挂的

注意：以下内容中标为斜体的是需要按照题目要求具体情况具体分析的，文章中的操作和代码是对板子题而言的

下面是板子题的完整代码（区间加法，区间求和）

#include<bits/stdc++.h>
#define int long long
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid (s + ((t - s) >> 1))
using namespace std;
const int MX = 4000055;
int a[MX],sum[MX],lz[MX];
void build(int s,int t,int p) {
	if(s == t) {
		sum[p] = a[s];
		return;
	}
	build(s,mid,ls);
	build(mid + 1,t,rs);
	sum[p] = sum[ls] + sum[rs];
}
void pushdown(int p,int s,int t) {
	if(lz[p]) {
		sum[ls] += lz[p] * (mid - s + 1);
		sum[rs] += lz[p] * (t - mid);
		lz[ls] += lz[p];
		lz[rs] += lz[p];
		lz[p] = 0;
	}
}
void update(int l,int r,int s,int t,int p,int v) {
	if(s >= l && t <= r) {
		sum[p] += v * (t - s + 1);
		lz[p] += v;
		return; 
	}
	pushdown(p,s,t);
	if(l <= mid) update(l,r,s,mid,ls,v);
	if(r >= mid + 1) update(l,r,mid + 1,t,rs,v);
	sum[p] = sum[ls] + sum[rs]; 
}
int query(int l,int r,int s,int t,int p) {
	if(s >= l && t <= r) return sum[p];
	pushdown(p,s,t);
	int ans = 0;
	if(l <= mid) ans += query(l,r,s,mid,ls);
	if(r >= mid + 1) ans += query(l,r,mid + 1,t,rs);
	return ans;
} 
signed main()
{
	int op,x,y,k,n,q;
	scanf("%lld%lld",&n,&q);
	for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
	build(1,n,1);
	for(int i = 1;i <= q;i++) {
		scanf("%lld",&op);
		if(op == 1) {
			scanf("%lld%lld%lld",&x,&y,&k);
			update(x,y,1,n,1,k);
		}
		else {
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

我们接下来慢慢分析（勿喷

#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid (s + ((t - s) >> 1))

一大堆莫名其妙的define。
把左儿子编号、右儿子编号和中间位置缩略了一下。

以下的代码中，

a[]代表原数列，sum[]代表区间的和，lz[]代表懒标记，
l、r代表目标区间的左右端点，s、t代表当前操作区间的左右端点，p代表当前操作区间的编号。

void build(int s,int t,int p) {
	if(s == t) {
		sum[p] = a[s];
		return;
	}
	build(s,mid,ls);
	build(mid + 1,t,rs);
	sum[p] = sum[ls] + sum[rs];
}

这段代码是用来建树的，首先，如果当前区间的左右端点相等（也就是只有一个点）， 那就把它的sum值赋值为原数列中对应位置的数（一个数的和不就是他自己吗）

否则，就不断对左右子区间递归操作，直到区间只有一个数。

最后，不要忘了将每个区间的sum值赋值为它左右两个子区间sum值的和。

void pushdown(int p,int s,int t) {
	if(lz[p]) {
		sum[ls] += lz[p] * (mid - s + 1);
		sum[rs] += lz[p] * (t - mid);
		lz[ls] += lz[p];
		lz[rs] += lz[p];
		lz[p] = 0;
	}
}

这段代码是用来下放懒标记的。

首先解释一下懒标记的作用：

如果某次要求对一个大区间进行修改，那么正常来说每次修改的时候都要对它的子区间进行更新以保证正确性+，但是这样的时间复杂度无法接受，是\(O(N)\)的、

那么如何优化呢？
那就是，当每次修改大区间的时候只对大区间的维护值进行更新，而其子区间的维护值等到需要查询或修改的时候再更新。
这样做的话可以优化掉大量不必要的操作，从而降低时间复杂度，使得线段树的时间复杂度为\(O(nlogn)\)的。
这就很nice。

sum[ls] += lz[p] * (mid - s + 1);
sum[rs] += lz[p] * (t - mid);

这两句的作用是用父区间的懒标记更新左右子区间的维护值。

lz[ls] += lz[p];
lz[rs] += lz[p];
lz[p] = 0;

这三句的作用是更新左右子区间的懒标记（因为只更新了“儿子”区间的维护值，“孙子”区间的维护值还没更新呢，需要将父区间的懒标记下传给“儿子”区间以正确更新“孙子”区间）并清空父区间的懒标记。

void update(int l,int r,int s,int t,int p,int v) {
	if(s >= l && t <= r) {
		sum[p] += v * (t - s + 1);
		lz[p] += v;
		return; 
	}
	pushdown(p,s,t);
	if(l <= mid) update(l,r,s,mid,ls,v);
	if(r >= mid + 1) update(l,r,mid + 1,t,rs,v);
	sum[p] = sum[ls] + sum[rs]; 
}

这段代码的作用是更新区间。
如果目标区间完全覆盖了当前操作区间，那么直接更新当前操作区间的维护值。 更新方法具体情况具体分析，比如板子题要求区间加法，给区间内的每个数都加上一个值，那么区间和的更新量就是区间元素数量乘以要加的值。
如果没有完全覆盖，就先下放当前区间的懒标记以保证正确性（否则子区间的更新量可能会是错误的），然后递归更新左右子区间。

最后，将父区间的维护值更新为左右子区间的和。注意这里要写“=”而不是“+=”！

 int query(int l,int r,int s,int t,int p) {
	if(s >= l && t <= r) return sum[p];
	pushdown(p,s,t);
	int ans = 0;
	if(l <= mid) ans += query(l,r,s,mid,ls);
	if(r >= mid + 1) ans += query(l,r,mid + 1,t,rs);
	return ans;
} 

这段代码是用来对区间求和的。
同样，如果目标区间覆盖了当前操作区间，直接返回当前操作区间的维护值；否则，先下放懒标记，然后递归处理左右子区间，最后返回答案。

以上就是线段树的基本框架（以板子题为例），本文持续更新中。