线段树笔记

线段树是用于解决区间问题的一种数据结构，用了分治思想。顾名思义“线段树”，它的每个点都是一段线段，维护着一个数组区间。线段树咨询速度很快，修改也很方便。

既然是分治，那么，一个递归操作就包含结束条件、分别递归和合并处理三个部分。

一个最基本的的线段树会包含以下几个函数👇

build() ———— 用于建树
modify() ——— 用于修改单点元素
query() ——— 用于咨询区间元素

而且，tree[x]一般表示为x节点的区间值（比如区间最大值，区间和之类的），并不需要存储区间开头或结尾。

除此之外，还有区间修改，一般常用的有懒惰标记和标记永久化两个方法。懒惰标记的方法实现需要一个额外的lazy数组，用来标记操作。与单点修改不同的是，懒惰标记不需要递归到底层，只需要在包含的修改区间标记一下，如果别的操作遍历过这个节点，再顺便把标记应用到子节点（一般为push_down()函数）。懒惰标记的核心思想是：不使用就不会应用（到子节点）真懒。大大减少了时间复杂度，一般最坏时间复杂度为O(log n) 。~~可能吧~~

线段树用于解决区间问题，比如区间最大值，区间和之类的，还有 RMQ 问题。

不说了，上代码：

#include <bits/stdc++.h>
#define int long long
//#define max(a,b) (a>b?a:b)
using namespace std;
//struct linetree
//{
int a[1000000],t[1000000],lazy[1000000];
void build(int l, int r, int x)
{
	if (l==r)
	{
		t[x]=a[l]; 
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	t[x]=max(t[x*2+1],t[x*2]);
	return;
}
void push_down(int x)
{
//	t[x]+=lazy[x];
	lazy[x*2]+=lazy[x];
	t[x*2]+=lazy[x];
	lazy[x*2+1]+=lazy[x];
	t[x*2+1]+=lazy[x];
	lazy[x]=0;
}
int query(int l, int r, int x, int L, int R)
{
	if (lazy[x]) push_down(x);
	if (l > R || r < L) return -0x7fffffff;
//	if (l == r) return t[x];
	if (L <= l && r <= R) return t[x];
	int mid=(l+r)/2,ans=-2000000000;
	
	ans=max(ans,query(l,mid,x*2,L,R));
	ans=max(ans,query(mid+1,r,x*2+1,L,R));
	return ans;
}
void modify(int l, int r, int x, int T, int v)
{
	if (l==r) 
	{
		a[T]=v;
		t[x]=v;
		return;
	}
	int mid=(l+r)/2;
	if (lazy[x]) push_down(x);
	if (T <= mid) modify(l,mid,x*2,T,v);
	else modify(mid+1,r,x*2+1,T,v);
	t[x]=max(t[x*2+1],t[x*2]);
	return;
}

void modifymax(int l, int r, int x, int L, int R, int value)
{
	if (l >= L && r <= R)
	{
		lazy[x]+=value;
		t[x]+=value;
		return;
	}
//	if (l > R || r < L) return;
	if (lazy[x]) push_down(x);
	int mid=(l+r)/2;
	if (L <= mid)modifymax(l,mid,x*2,L,R,value);
	if (R > mid) modifymax(mid+1,r,x*2+1,L,R,value);
	t[x]=max(t[x*2],t[x*2+1]);
}
//};
signed main()
{
	int n,m,x,y,z;
	scanf("%lld",&n);
	for (int i = 1 ; i <= n ; ++i) scanf("%lld",&a[i]);
	build(1,n,1);
	scanf("%lld",&m);
	for (int i = 0 ; i < m ; ++i) 
	{
		scanf("%lld",&x);
		if (x == 1)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			modifymax(1,n,1,x,y,z);
		} else {
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(1,n,1,x,y));
		}
	}
	return 0;
}

其他

一些GMOJ上的例题：