线段树总结

线段树总结—By Zach

本蒟蒻的总结仅供参考。。。

一、关于树状数组和线段树

树状数组（二叉索引树）：一般而言，用于序列满足区间可减性、优先级相同的运算中。例如，前缀和、差分、前缀异或和等等；代码短，易于调试，易扩展到二维；
zkw线段树：一般而言，用于序列最值等二叉索引树不能完成的带修区间最值问题。注意：不可用于优先级不同的修改！！相较于线段树代码较短，易于调试；
线段树：zkw能做的都能做，可以变身为可持续化线段树。

二、典型套路总结

优先级不同的运算

例题：[AHOI2009] 维护序列

我们考虑将整个操作转化：先乘再加；

如果都是单一的两种运算，延迟标记能做到这一点；那么当两者混合的时候，我们怎么办呢？

想象这样一种情况：区间\([l,r]\)（原始序列），先乘了一个数\(x\)，再加上一个数\(y\)。那么我们对于这样的操作就是分别计算到延迟标记中，乘的那个数统计到乘法延迟标记当中，假发一样。

这时候这个区间又来了一个乘法（乘数记成\(z\)），那么我们就应该先\(z*y\)，将加法延迟标记修改，再修改乘法延迟标记，进而修改到\(y*z\)。

也就是当进了一个加法操作，直接累加；进了一个乘法操作，修改加法延迟标记，再修改它本身的。

下放怎么办？我们可以将两种运算分离，乘法先下放。这样一来，我们把两种优先级不同的运算巧妙地合在了一起。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int MAXN = 100000 + 5;

typedef long long LL;

int n, m;
LL mod;

struct Segment
{
	LL sum;
	LL flag_prob, flag_add;
	void init(LL val)
	{
		sum = val, flag_prob = 1, flag_add = 0;
	}
	inline void merge(Segment x, Segment y)
	{
		sum = (x.sum + y.sum) % mod, flag_prob = 1, flag_add = 0;
	}
} T[MAXN << 2];

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;	
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}
void spread(int p, int l, int r)
{
	if((T[p].flag_add || T[p].flag_prob != 1) && l != r)
	{	
		int mid = l + ((r - l) >> 1);
		T[p << 1].sum = 1ll * T[p << 1].sum * T[p].flag_prob % mod;
		T[p << 1].sum = (T[p << 1].sum + 1ll * (mid - l + 1) * T[p].flag_add % mod) % mod;
		T[p << 1 | 1].sum = 1ll * T[p << 1 | 1].sum * T[p].flag_prob % mod;
		T[p << 1 | 1].sum = (T[p << 1 | 1].sum + 1ll * (r - mid) * T[p].flag_add % mod) % mod;
		T[p << 1].flag_prob = 1ll * T[p << 1].flag_prob * T[p].flag_prob % mod;
		T[p << 1 | 1].flag_prob = 1ll * T[p << 1 | 1].flag_prob * T[p].flag_prob % mod;
		T[p << 1].flag_add = (1ll * T[p << 1].flag_add * T[p].flag_prob % mod + T[p].flag_add) % mod;
		T[p << 1 | 1].flag_add = (1ll * T[p << 1 | 1].flag_add * T[p].flag_prob % mod + T[p].flag_add) % mod;
	}
	T[p].flag_prob = 1, T[p].flag_add = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val % mod);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify_I(int p, int l, int r, int L, int R, LL val)//����Ӳ��� 
{
	if(l >= L && r <= R)
	{
		T[p].sum = (T[p].sum + 1ll * (r - l + 1) * val % mod) % mod;
		T[p].flag_add = (T[p].flag_add + val) % mod;
		return;
	}
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify_I(lson, L, R, val);
	if(R > mid) modify_I(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify_II(int p, int l, int r, int L, int R, LL val)//����˲��� 
{
	if(l >= L && r <= R)
	{
		T[p].sum = 1ll * val * T[p].sum % mod;
		T[p].flag_add = 1ll * T[p].flag_add * val % mod;
		T[p].flag_prob = 1ll * T[p].flag_prob * val % mod;
		return;
	}
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify_II(lson, L, R, val);
	if(R > mid) modify_II(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

LL query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum;
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	LL val = 0;
	if(L <= mid) val = (val + query(lson, L, R)) % mod;
	if(R > mid) val = (val + query(rson, L, R)) % mod; 
	return val;
}

int main()
{
	read(n), read(mod);
	build(wht);
	read(m);	
	int opt, l, r; 
	LL v;
	FOR(i, 1, m)
	{
		read(opt);
		read(l);
		read(r);
		if(opt == 1)
		{
			read(v);
			modify_II(wht, l, r, v);
		}
		else if(opt == 2)
		{
			read(v);
			modify_I(wht, l, r, v);
		}
		else printf("%lld\n", query(wht, l, r));
	}
	return 0;
}

最大子段和类问题

例题：小白逛公园

维护这样几个量：区间前缀最大值、后缀最大值、区间最大值、区间和。

区间最大值可以有各个区间的最大值或者左子区间的后缀最大值\(+\)右子区间的前缀最大值拼成。这样一来，问题就解决了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define pii pair<int,int>
#define mp(x, y) make_pair(x,y)
using namespace std;

const int MAXN = 6e5 + 5, INF = 1e9;

typedef long long LL;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;	
	return;
}

struct Segment
{
	LL lmax, rmax, val_max, sum;
	void init(LL val)
	{
		lmax = rmax = val_max = sum = val;
	}
} T[MAXN << 2];

Segment operator +(Segment &x, Segment &y)
{
	Segment res;
	res.sum = x.sum + y.sum;
	res.lmax = max(x.lmax, x.sum + y.lmax), res.rmax = max(y.rmax, y.sum + x.rmax);
	res.val_max = max(max(x.val_max, y.val_max), max(max(res.lmax, res.rmax), x.rmax + y.lmax));
	return res;
}

int n, m;
void build(int p, int l, int r)
{
	if(l == r)
	{
		LL v;
		read(v), T[p].init(v);
		return;	
	}	
	int mid = l + ((r - l) >> 1); 
	build(lson), build(rson);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

void modify(int p, int l, int r, int pos, LL val)
{
	if(l == r)
	{
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modify(lson, pos, val); 
	else modify(rson, pos, val);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

Segment query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p];
	int mid = l + ((r - l) >> 1);
	Segment t1, t2;
	if(R <= mid) return query(lson, L, R);
	if(L > mid) return query(rson, L, R);
	t1 = query(lson, L, R), t2 = query(rson, L, R);
	return t1 + t2;
}

int main()
{
	read(n), read(m);
	build(wht);
	int k, a, b, p, s;
	FOR(i, 1, m)
	{
		read(k);
		if(k == 1)
		{
			read(a), read(b);
			if(a > b) swap(a, b);
			printf("%lld\n", query(wht, a, b).val_max);
		}
		else
		{
			read(p), read(s);
			modify(wht, p, s);
		}
	}
	return 0;
}

差分

例题：gcd区间

加强：区间修改。

题目看起来比较困难，但实际上通过推式子得到。

\[(x,y,z)=(x,y-x,z-y)
\]

由此可以晓得对于\(n\)元均成立。

这启发我们用线段树维护差分序列求\((x,y)\)，区间修改在差分序列中最转化为单点修改。这样一来，我们就将看似困难的问题解决了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

#define re register
#define U unsigned
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
#define CLR(x,y) memset(x,y,sizeof(x))
#define FOR(i,x,y) for(re int i=x;i<=y;++i)
#define SFOR(i,u,v,w) for(re int i=u;i<=v;i+=w)
#define ROF(i,x,y) for(re int i=x;i>=y;--i)
#define SROF(i,u,v,w) for(re int i=u;i>=v;i-=w)
#define DEBUG(x) printf("Test#: %d\n", x)
using namespace std;

const int MAXN = 1000 + 5;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
}

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd(y, x % y);
}

struct Segment
{
	int d;
	inline void init(int val)
	{
		d = abs(val);
		return;
	}
	inline void merge(Segment x, Segment y)
	{
		d = gcd(x.d, y.d);
		return;
	}
} T[MAXN << 2];

int n, m, a[MAXN];

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].init(a[l] - a[l - 1]);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(r < L || l > R) return 1;
	if(l >= L && r <= R) return T[p].d;
	int mid = l + ((r - l) >> 1), val;
	if(L > mid) val = query(rson, L, R);
	else if(R <= mid) val = query(lson, L, R);
	else val = gcd(query(lson, L, R), query(rson, L, R));
	return val;
}

int main()
{
	read(n), read(m);
	a[0] = 0;
	FOR(i, 1, n) read(a[i]);
	build(wht);
	int L, R;
	while(m --)
	{
		read(L), read(R);
		if(L == R) printf("%d\n", a[L]);
		else printf("%d\n", gcd(a[L], query(wht, L + 1, R)));
	}
	return 0;
}

懒标记

例题：方差

区间加就区间加，平均数就是区间和类操作，方差怎么办？

考虑到：

\[\sum_{i=l}^r(a_i-a)^2/n=\sum_{i=l}^ra_i^2/n-a^2
\]

可以知道：平方和、求和均维护。

反观加法，可以通过推式子分别维护。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int N = 1e5 + 7;

typedef double db;
template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return; 
}
struct Segment
{
	db sum, prob, flag;
	void init(db val)
	{
		sum = val;
		prob = val * val;
		flag = 0;
	}	
} T[N << 2];

int n, m;
Segment operator +(Segment &x, Segment &y)
{
	Segment res;
	res.flag = 0;
	res.sum = x.sum + y.sum; 
	res.prob = x.prob + y.prob; 
	return res;
}

inline void spread(int p, int l, int r)
{
	if(T[p].flag && l != r)
	{
		int mid = l + ((r - l) >> 1);
		T[p << 1].flag += T[p].flag;
		T[p << 1].prob += T[p << 1].sum * T[p].flag * 2 + 1ll * (mid - l + 1) * T[p].flag * T[p].flag;
		T[p << 1].sum += 1ll * (mid - l + 1) * T[p].flag;
		T[p << 1 | 1].flag += T[p].flag;
		T[p << 1 | 1].prob += T[p << 1 | 1].sum * T[p].flag * 2 + 1ll * (r - mid) * T[p].flag * T[p].flag;
		T[p << 1 | 1].sum += 1ll * (r - mid) * T[p].flag;
	}
	T[p].flag = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		db val;
		scanf("%lf", &val), T[p].init(val);		
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

void modify(int p, int l, int r, int L, int R, db val)
{
	if(l >= L && r <= R)
	{
		T[p].prob += T[p].sum * val * 2 + 1ll * (r - l + 1) * val * val;
		T[p].sum += 1ll * (r - l + 1) * val;
		T[p].flag += val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	spread(p, l, r);
	if(L <= mid) modify(lson, L, R, val);
	if(R > mid) modify(rson, L, R, val);
	T[p] = T[p << 1] + T[p << 1 | 1];
	return;
}

Segment query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p];
	spread(p, l, r);
	
	Segment res, tmp1, tmp2;
	int mid = l + ((r - l) >> 1);
	if(R <= mid) return query(lson, L, R);
	if(L > mid) return query(rson, L, R);
	tmp1 = query(lson, L, R), tmp2 = query(rson, L, R);
	res = tmp1 + tmp2;
	return res;
}

int main()
{
	read(n), read(m);
	build(wht);
	int op, x, y;
	db k;
	Segment tmp;
	FOR(i, 1, m)
	{
		read(op);
		if(op == 1)
		{
			read(x), read(y);
			scanf("%lf", &k);
			modify(wht, x, y, k);
		}
		else if(op == 2)
		{
			read(x), read(y);
			db res = query(wht, x, y).sum;
			printf("%.4lf\n", (double)res / (y - x + 1));
		} 
		else
		{ 
			read(x), read(y);
			tmp = query(wht, x, y);
			db sum = tmp.sum, prob = tmp.prob;
			int len = y - x + 1;
			printf("%.4lf\n", (double)(prob * len - sum * sum) / len / len);
		}
	}
	return 0;
}

例题：区间加区间sin和

_{lxl出的题，但很水。}

三角的和差公式。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> 
#include<cmath>
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(register int i=x;i<=y;++i)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;

const int N = 2e5 + 5;

typedef double db;
typedef long long LL;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true; 
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}

struct Segment
{
	LL flag;
	db sum_sin, sum_cos;	
	void init(LL val)
	{
		flag = 0, sum_sin = sin((db)val), sum_cos = cos((db)val);
	}
	void merge(Segment x, Segment y)
	{
		flag = 0;
		sum_sin = x.sum_sin + y.sum_sin;
		sum_cos = x.sum_cos + y.sum_cos;		
	}
} T[N << 2];

db sink, cosk;
int n, m;

void spread(int p, int l, int r)
{
	if(T[p].flag && l != r)
	{
		LL val = T[p].flag; db sin0, cos0;
		sin0 = T[p << 1].sum_sin, cos0 = T[p << 1].sum_cos;
		T[p << 1].flag += val, T[p << 1].sum_sin = sin0 * cos((db)val) + cos0 * sin((db)val), T[p << 1].sum_cos = cos0 * cos((db)val) - sin0 * sin((db)val);
		sin0 = T[p << 1 | 1].sum_sin, cos0 = T[p << 1 | 1].sum_cos;
		T[p << 1 | 1].flag += val, T[p << 1 | 1].sum_sin = sin0 * cos((db)val) + cos0 * sin((db)val), T[p << 1 | 1].sum_cos = cos0 * cos((db)val) - sin0 * sin((db)val);		
	}
	T[p].flag = 0;
	return;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
 	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modify(int p, int l, int r, int L, int R, int val)
{
	if(l >= L && r <= R)
	{
		T[p].flag += val;
		db sin0 = T[p].sum_sin, cos0 = T[p].sum_cos;
		T[p].sum_sin = sin0 * cosk + cos0 * sink, T[p].sum_cos = cos0 * cosk - sin0 * sink;
		return;
	}
	LL mid = l + ((r - l) >> 1);
	spread(p, l, r);
	if(L <= mid) modify(lson, L, R, val);
	if(R > mid) modify(rson, L, R, val);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}

db query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum_sin;
	spread(p, l, r);
	int mid = l + ((r - l) >> 1);
	db res = 0.00;
	if(L <= mid) res += query(lson, L, R);
	if(R > mid) res += query(rson, L, R);
	return res;
}

int main()
{
	read(n);
	build(wht);
	
	int opt, l, r, val;
	read(m);
	FOR(i, 1, m)
	{
		read(opt);
		if(opt == 1)
		{
			read(l), read(r), read(val);
			sink = sin(val);
			cosk = cos(val);
 			modify(wht, l, r, val);
		}
		else 
		{
			read(l), read(r);
 			printf("%.1lf\n", query(wht, l, r));
		}
	}
	return 0;
}

区间重复类

这一类问题常常有描述：区间数互不相同、存在数值相同的区间、存在两个数值和是定值的区间

对于这一类问题，我们常常会对于每一个数值开一个\(set\)，在\(set\)里找前驱和后继，线段树维护前驱最大值，转化为判断区间最值。

例题：查找 Search

对于一个数，维护最大前驱；一个数，同时维护它的前驱（即与它相等的、在它前面的最大位置）

它的”互补前驱“（即与它和为给定值、在它前面的最大位置）它的后继以及”互补“后继。

更改的时候要同时对后继更改。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>

#define fi first
#define se second
#define re register
#define U unsigned
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
#define pii pair<int,int>
#define MP make_pair
#define CLR(x,y) memset(x,y,sizeof(x))
#define FOR(i,x,y) for(re int i=x;i<=y;++i)
#define SFOR(i,u,v,w) for(re int i=u;i<=v;i+=w)
#define ROF(i,x,y) for(re int i=x;i>=y;--i)
#define SROF(i,u,v,w) for(re int i=u;i>=v;i-=w)

using namespace std;

const int N = 5e5 + 5;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x;
	return;
}

struct Segment
{
	int pre_max;
} T[N << 2];


set <int> table[N];

typedef set<int>::iterator iter;
int n, m, w, a[N], b[N];

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].pre_max = 0;
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].pre_max = 0;
	return;
}

void modify(int p, int l, int r, int pos, int pre_val)//单点修改 
{
	if(l == r)
	{
		T[p].pre_max = pre_val;	
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modify(lson, pos, pre_val);
	else modify(rson, pos, pre_val);
	T[p].pre_max = max(T[p << 1].pre_max, T[p << 1 | 1].pre_max);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(r < L || l > R) return 0;
	if(l >= L && r <= R) return T[p].pre_max;
	int mid = l + ((r - l) >> 1), val = 0;
	if(L <= mid) val = query(lson, L, R);
	if(R > mid) val = max(val, query(rson, L, R));
	return val;
}

int pre(int x)
{
	iter it1 = table[a[x]].lower_bound(x), it2 = table[w - a[x]].lower_bound(x);
	if(it2 == table[w - a[x]].begin()) return 0;
	else if(it1 == table[a[x]].begin()) return *--it2;
	else if(*--it1 > *--it2) return 0;
	return *it2;	
}
vector <int> res;
int main()
{
	read(n), read(m), read(w);
	FOR(i, 1, n) read(a[i]);
	build(wht);
	FOR(i, 1, n)
	{
		modify(wht, i, pre(i));	
		table[a[i]].insert(i);
	}
	int op, pos, val, l, r, cnt = 0;
	while(m --)
	{
		read(op);
		if(op == 1)
		{
			int pos, val;
			read(pos), read(val);// 修改5个量：pre1[pos] pre2[pos] nxt1[pos]相关 nxt2[pos]相关
			res.clear();
			// modify pos
			iter it1 = table[a[pos]].upper_bound(pos), it2 = table[w - a[pos]].lower_bound(pos);
			if(it1 != table[a[pos]].end()) res.push_back(*it1);
			if(it2 != table[w - a[pos]].end()) res.push_back(*it2);
			table[a[pos]].erase(pos);
			table[val].insert(pos), a[pos] = val;
			res.push_back(pos);
			it1 = table[a[pos]].upper_bound(pos), it2 = table[w - a[pos]].lower_bound(pos);
			if(it1 != table[a[pos]].end()) res.push_back(*it1);
			if(it2 != table[w - a[pos]].end()) res.push_back(*it2);
			for(int i = 0; i < res.size(); ++ i) modify(wht, res[i], pre(res[i]));
		}
		else
		{
			int l, r;
			read(l), read(r);
			l ^= cnt, r ^= cnt;
			if(query(wht, l, r) >= l) puts("Yes"), ++ cnt;
			else puts("No");
		}	
	}
	return 0;
}

例题：算术天才⑨与等差数列

形成等差数列的充要条件是：最大值和最小值范围固定在某一段、区间两两数差的GCD为公差的倍数、元素不重复。

维护最大值和最小值，区间GCD（差分做法），和上述前驱做法。对于每一个出现的值开一个\(STL\) \(set\)。又要强制在线，直接开map求离散化。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath> 
#include<map>
#include<set>

#define Re register
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(Re int i=x;i<=y;++i)
#define SFOR(i, u, v, w) for(Re int i=u;i<=v;i+=w)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define DEBUG(x) printf("Test: %d\n", x) 

using namespace std;

const int MAXN = 3e5 + 5;

typedef set <int> ::iterator iter;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	if(mark) x = -x; 
	return;
}

int gcd(int x, int y)
{
	if(!y) return x;
	return gcd(y, x % y);
}

map <int, int> table;
set <int> s[MAXN << 1];

int n, m, tot = 0, a[MAXN];

struct Segment
{
	int vmin, vmax, d, pre_max;
} T[MAXN << 2];

inline struct Segment merge(struct Segment x, struct Segment y)
{
	struct Segment p;
	p.vmax = max(x.vmax, y.vmax), p.vmin = min(x.vmin, y.vmin);
	p.d = gcd(x.d, y.d), p.pre_max = max(x.pre_max, y.pre_max);
	return p;
}

void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].vmax = T[p].vmin = a[l];
		T[p].d = abs(a[l] - a[l - 1]);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void modifyI(int p, int l, int r, int pos, int val) //修改区间最值 
{
	if(l == r)
	{
		T[p].vmax = T[p].vmin = val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyI(lson, pos, val);
	else modifyI(rson, pos, val);
	T[p] = merge(T[p << 1], T[p << 1 | 1]); 
	return;	
}

void modifyII(int p, int l, int r, int pos, int val) //修改区间gcd 
{
	if(l == r)
	{
		T[p].d = abs(val);	
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyII(lson, pos, val);
	else modifyII(rson, pos, val);	
	T[p].d = gcd(T[p << 1].d, T[p << 1 | 1].d);
	return;
}

void modifyIII(int p, int l, int r, int pos, int val) // 修改区间最大前驱 
{
	if(l == r)
	{
		T[p].pre_max = val;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(pos <= mid) modifyIII(lson, pos, val);
	else modifyIII(rson, pos, val);
	T[p].pre_max = max(T[p << 1].pre_max, T[p << 1 | 1].pre_max);
	return;
}

Segment query(int p, int l, int r, int L, int R) // 区间最值 区间GCD pre_max 查询 
{
	if(l >= L && r <= R) return T[p];
	int mid = l + ((r - l) >> 1);
	if(L > mid) return query(rson, L, R);
	if(R <= mid) return query(lson, L, R);
	Segment x = query(lson, L, R), y = query(rson, L, R);
	return merge(x, y);
}

int pre(int x)
{
	iter it = s[table[a[x]]].find(x);
	if(it == s[table[a[x]]].begin()) return 0; //没有前驱 
	return (*--it);
}
int nxt(int x)
{
	iter it = s[table[a[x]]].find(x);
	if((++ it) == s[table[a[x]]].end()) return 0;
	return *it;
}

int main()
{
	read(n), read(m);
	a[0] = 0;
	FOR(i, 1, n) read(a[i]);
	FOR(i, 1, m + n) s[i].clear();
	build(wht);
	table.clear(), table[0] = 0;
	FOR(i, 1, n)
	{
		if(table.find(a[i]) == table.end()) table[a[i]] = ++ tot;
		s[table[a[i]]].insert(i);
		modifyIII(wht, i, pre(i));
	}
	int cnt = 0, op, x, y, l, r, k;
	FOR(i, 1, m)
	{
		read(op);
		if(op == 1)
		{
			read(x), read(y);
			x ^= cnt, y ^= cnt;
			if(table.find(y) == table.end()) table[y] = ++ tot;
			modifyI(wht, x, y);
			modifyII(wht, x, y - a[x - 1]), modifyII(wht, x + 1, a[x + 1] - y);
			int tmp = nxt(x);
			if(tmp) modifyIII(wht, tmp, pre(x));
			s[table[a[x]]].erase(x);
			s[table[a[x] = y]].insert(x);
			modifyIII(wht, x, pre(x));
			tmp = nxt(x);
			if(tmp) modifyIII(wht, tmp, x);
		}
		else
		{
			read(l), read(r), read(k);
			l ^= cnt, r ^= cnt, k ^= cnt;
			if(l == r) 
			{
				++ cnt, puts("Yes");
				continue;
			}
			Segment t1 = query(wht, l, r);
			if(k == 0) 
			{
				if(t1.vmax == t1.vmin) ++ cnt, puts("Yes");
				else puts("No");
				continue;
			}
			Segment t2 = query(wht, l + 1, r);
			if(t2.d % k == 0 && (t1.vmax - t1.vmin) == 1ll * k * (r - l) && t1.pre_max < l) 
				++ cnt, puts("Yes");
			else puts("No");
		}
	}
	return 0;	
} 

//solution:
/*  
询问区间[l, r], 问该区间是否构成公差为 k 的等差数列 
1. 维护每个区间最大值, 最小值, VMAX-VMIN = (r - l)*k ;
2. 维护差分数组的gcd, 即当queryII(l+1,r)为k的倍数 时满足; 
3. 保证区间内两两之间互不相等, 则预处理区间内 每个数的前驱在哪里, 区间内前驱下标(queryIII(l+1,r))小于l才行
考虑到数的值比较大, 离散化一下(map!!!);
修改Ax=y: (单点修改) 
1. 单点修改区间最值
2. 差分b[x]=Ax-Ax-1, b[x+1]=Ax+1-Ax, 动态维护gcd;
3. 对于每一个值建一个set, 那么对于Ax它的后继要改, 前驱不变, 新的set后继改, 前驱不变 
*/

非标记做法

这一类问题有一个特点：区间修改的操作无法进行延迟标记……

比方说，区间\(ln\)，对于每一个数向下取整（保证实数域有意义），区间和。会发现对于一个数，操作次数过多结果会一样。只有前面的操作会影响维护的值，当该数减到\(0\)的时候不会再进行操作。因此，我们只需要记录一下最大有效操作数即可，小于等于上限暴力修改，大于不管。很套路。

例题：上帝造题的七分钟2

这道题对于区间开方。其实开多少次方题目无影响。

会发现一个数：\(\sqrt{\sqrt{ \sqrt{\sqrt{\sqrt{\sqrt{\sqrt{…}}}}}}\)操作数有上限。

因此我们记录操作数上限即可，不超过该数暴力修改，大于就置之不理。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define wht 1,1,n
using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 5, INF = 1 << 30;

template <typename T> void read(T &x)
{
	bool mark = false;
	char ch = getchar();
	for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
	for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';	
	if(mark) x = -x;
	return;
}

struct Segment
{
	LL sum;
	int cnt;
	void init(LL val)
	{
		sum = val, cnt = 0;	
	} 
	void merge(Segment x, Segment y)
	{
		sum = x.sum + y.sum, cnt = min(x.cnt, y.cnt);
	}
} T[MAXN << 2];
int n, m, limit = 15;
void build(int p, int l, int r)
{
	if(l == r)
	{
		LL val;
		read(val);
		T[p].init(val);
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}
void modify(int p, int l, int r, int L, int R)
{
	if(T[p].cnt >= limit) return;
	if(l == r)
	{
		T[p].sum = (int)sqrt(T[p].sum);
		++ T[p].cnt;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify(lson, L, R);
	if(R > mid) modify(rson, L, R);
	T[p].merge(T[p << 1], T[p << 1 | 1]);
	return;
}
LL Query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum;
	int mid = l + ((r - l) >> 1);
	LL res = 0;
	if(L <= mid) res += Query(lson, L, R);
	if(R > mid) res += Query(rson, L, R);
	return res;
}
int main()
{
	read(n);
	build(wht);
	read(m);	
	int opt, l, r;
	while(m --)
	{
		read(opt), read(l), read(r);
		if(l > r) swap(l, r);
		if(!opt) modify(wht, l, r);
		else printf("%lld\n", Query(wht, l, r));
	}
	return 0;
}

例题：[六省联考 2017] 相逢是问候

很毒瘤！

这题居然和模数有了关系。

扩展欧拉定理：

\[a^b=a^{b\ mod\phi(n) +\phi(n)}(mod\ n)(b>=\phi(n))
\]

考虑不断操作的过程，总会有一次\(\phi_{(…)}(p)=1\)，所以我们预处理出该有效次数。

但由于每一次都不是连续的（模数都不相同），所以我们不能直接像开方那样直接操作。我们需要预处理出每次的操作次数下的答案。

由于扩展欧拉定理只能在指数大于模数的时候用，所以我们在处理的时候要记录指数是否超过了模数，进行递推。

但由于时间复杂度还是不够，我们直接将\(c^a\)分解为\(c^{a\ mod\ 10000}*c^{a/10000}*c^{10000}\)数要与处理出来。

具体来说，我们可以定义一个递推式：\(d[i,j,k]\)代表第\(i\)个数在进行到总共\(j\)次操作，当前处于\(\ mod\ \phi_{(k)}(p)\)阶段，有：\(d[i,j,k]=c^{d[i,j-1,k+1]}\ mod\ \phi(k)\)。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register
#define CLR(x, y) memset(x,y,sizeof(x))
#define FOR(i, x, y) for(Re int i=x;i<=y;++i)
#define SFOR(i, u, v, w) for(Re int i=u;i<=v;i+=w)
#define wht 1,1,n
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define DEBUG(x) printf("Test: %d\n", x) 
using namespace std;

typedef long long LL;

const int MAXN = 5e4 + 5, MAX_lim = 30, SIZE = 1e4 + 5;

int euler(int x)
{
	int res = x;
	for(int i = 2; i <= sqrt(x); ++ i)
	{
		if(x % i == 0)
		{
			res = res / i * (i - 1);
			while(x % i == 0) x /= i;
		}
		if(x == 1) return res;
	}
	if(x > 1) res = res / x * (x - 1);
	return res;
}

struct Segment
{
	int cnt, sum;
} T[MAXN << 2];

bool b1[MAX_lim][SIZE] = {}, b2[MAX_lim][SIZE] = {}, bd[MAXN][MAX_lim][MAX_lim] = {};
int n, m, mod, c, lim = 0, a[MAXN], phi[MAX_lim];
LL pow1[MAX_lim][SIZE], pow2[MAX_lim][SIZE], d[MAXN][MAX_lim][MAX_lim];

Segment merge(Segment s, Segment t)
{
	Segment x;
	x.cnt = min(s.cnt, t.cnt), x.sum = (s.sum + t.sum) % mod;
	return x;
}
void build(int p, int l, int r)
{
	if(l == r)
	{
		T[p].cnt = 0, T[p].sum = a[l] % mod;
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(lson), build(rson);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

void prework()
{	
	phi[0] = mod;
	while(phi[lim ++] > 1) phi[lim] = euler(phi[lim - 1]);
	phi[lim] = 1;
	FOR(i, 0, lim)
	{
		pow1[i][0] = 1;
		FOR(j, 1, 10000)
		{
			pow1[i][j] = 1ll * pow1[i][j - 1] * c;
			if(pow1[i][j] >= phi[i]) pow1[i][j] %= phi[i], b1[i][j] = 1;
			b1[i][j] |= b1[i][j - 1];			
		}
	}
	FOR(i, 0, lim)
	{
		pow2[i][0] = 1;
		b2[i][1] = b1[i][10000];
		FOR(j, 1, 10000)
		{
			pow2[i][j] = 1ll * pow2[i][j - 1] * pow1[i][10000];
			if(pow2[i][j] >= phi[i]) pow2[i][j] %= phi[i], b2[i][j] = 1;
			b2[i][j] |= b2[i][j - 1] | b1[i][10000];
		}
	}
	FOR(i, 1, n)
	{
		FOR(j, 0, lim)
		{
			d[i][0][j] = a[i] % phi[j];
			if(a[i] >= phi[j]) bd[i][0][j] = 1;
		}
		FOR(j, 1, lim)
		{
			d[i][j][lim] = 0;
			FOR(k, 0, lim - 1)
			{
				d[i][j][k] = 1ll * pow2[k][d[i][j - 1][k + 1] / 10000] * pow1[k][d[i][j - 1][k + 1] % 10000];
				bd[i][j][k] = b1[k][d[i][j - 1][k + 1] % 10000] | b2[k][d[i][j - 1][k + 1] / 10000];
				if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] |= 1;
				if(bd[i][j - 1][k + 1])
				{
					d[i][j][k] *= pow2[k][phi[k + 1] / 10000];					
					if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] = 1;
					d[i][j][k] *= pow1[k][phi[k + 1] % 10000];
					if(d[i][j][k] >= phi[k]) d[i][j][k] %= phi[k], bd[i][j][k] = 1;
					bd[i][j][k] |= b1[j][phi[k + 1] % 10000] | b2[j][phi[k + 1] / 10000];
				}
			}
		}
	}
	return;
}

void modify(int p, int l, int r, int L, int R)
{
	if(T[p].cnt >= lim) return;
	if(l == r)
	{
		++ T[p].cnt;
		T[p].sum = d[l][T[p].cnt][0] % mod;
		return;
	}
	int mid = l + ((r - l) >> 1);
	if(L <= mid) modify(lson, L, R);
	if(R > mid) modify(rson, L, R);
	T[p] = merge(T[p << 1], T[p << 1 | 1]);
	return;
}

int query(int p, int l, int r, int L, int R)
{
	if(l >= L && r <= R) return T[p].sum % mod;
	int mid = l + ((r - l) >> 1), val = 0;	
	if(L <= mid) val = query(lson, L, R) % mod;
	if(R > mid) val = (val + query(rson, L, R)) % mod;
	return val;
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &mod, &c);
	FOR(i, 1, n) scanf("%d", &a[i]);
	prework();
	build(wht);
	int op, l, r;
	FOR(i, 1, m)
	{
		scanf("%d %d %d", &op, &l, &r);	
		if(!op) modify(wht, l, r);
		else printf("%d\n", query(wht, l, r));
	}
	return 0;
}

本文链接：https://www.cnblogs.com/zach20040914/p/14304792.html

线段树总结