猫树 | Reincarnation

「末世追忆」：”松动爪子向前，无论路途艰险”

引言

在某日的中，有过这样一道题：

给定一个长度为的序列，有次询问，每次询问一个区间，求出一个区间，使得最大。

。

可见，这是一个线段树求区间子段和的模板题（具体见），甚至不带修改，然后默写一遍。稍微测了下样例，发现在上后面两个直接了，不过上勉强能过，交上一发，虽然有的时限，但还是只有。

没能跑过。

我们想想应该如何来优化，对于这道题，和相比，这道题并没有修改操作，而我们的代码可以无伤过修改。并且我们观察到这道题的大的离谱，但是稍微可依赖，所以考虑优化询问时间。那么我们思考一下，如果我们可以写一棵线段树，使其不支持修改，但是询问时间缩减的数据结构呢。

有！

这是一种类静态线段树，称为猫树（），不支持修改（其实支持），可以维护带有合并性质的区间操作，建树复杂度，询问复杂度。

猫树

实现

如果我们的询问时间短，那就要在预处理上下功夫。

在这道题的时候，我曾经考虑到一个做法，那就是记一个表示当前区间已经获得的价值。但这种记忆化明显不可行，因为我们当前并不知道是否拿到的是整区间或者是某一个散区间，导致无法记忆。

但我们可以换一个角度来思考，线段树的操作在于：将询问区间划分成并向下递归，合并所得到的答案区间，这样的理想复杂度是，不可优化。

那么，如果我们一开始就从向其父结点走，直到走到一个区间将这个区间完全包括，然后得到的答案，理想复杂度依然是，但可以发现一些性质：

当前我们得到的这个区间满足，并且是和的。
设有，一定有。通俗来讲，这个区间如果分裂的话，一定满足和不再同一个子区间。

那么，我们应该拿这个性质干什么捏。

我们可以通过两个端点的来得到其答案，但这样的复杂度虽然降低了，但事实上还是，每次查询的复杂度还未达到。

~~考虑 ST 表~~。

过于麻烦，因为事实上，我们可以深讨一些猫树的性质，因为本身上这还是一种类线段树，对于结点，其子结点就是和，这是显然的，也就发现，每一个子结点的编号来源于其父结点二进制位右移一位并取或的操作。

接下来读者可以验证：和的就是。那这有什么性质呢。我们可以多来几组，就会发现：

两个叶结点的就是其编号二进制位的（最长公共前缀）。

然后就可以用玄学位运算达到的查询时间力。

GSS I

给出代码。

const int MAXN=2e5+10;
int N,Q,Len,Val[MAXN],Lg[MAXN],Pos[MAXN],q[21][MAXN],s[21][MAXN];
#define ls p<<1
#define rs p<<1|1
void build(int p,int l,int r,int d)
{
	if(l==r) return Pos[l]=p,void();
	int prep,sum_,mid=(l+r)>>1;
	q[d][mid]=s[d][mid]=prep=sum_=Val[mid],checkMax(sum_,0);
    //处理左子区间
	for(int i=mid-1;i>=l;--i)
	{
		prep+=Val[i],sum_+=Val[i],s[d][i]=std::max(s[d][i+1],prep);
		q[d][i]=std::max(q[d][i+1],sum_),checkMax(sum_,0);
	}
	q[d][mid+1]=s[d][mid+1]=prep=sum_=Val[mid+1],checkMax(sum_,0);
	//处理右子区间
    for(int i=mid+2;i<=r;++i)
	{
		prep+=Val[i],sum_+=Val[i],s[d][i]=std::max(s[d][i-1],prep);
		q[d][i]=std::max(q[d][i-1],sum_),checkMax(sum_,0);
	}
    //同理线段树，递归建树
	build(ls,l,mid,d+1),build(rs,mid+1,r,d+1);
}
inline int query(int l,int r)
{
	if(l==r) return Val[l];
	int d=Lg[Pos[l]]-Lg[Pos[l]^Pos[r]];	//求得lca
	return std::max(std::max(q[d][l],q[d][r]),s[d][l]+s[d][r]);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N),Len=1;
	while(Len<N) Len<<=1;
	for(int i=1;i<=N;++i) read(Val[i]);
	for(int i=2,l=Len<<1;i<=l;++i) Lg[i]=Lg[i>>1]+1;
	build(1,1,Len,1);	//猫树按照二进制位建树，所以需要多建一部分
	read(Q);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		write(query(ql,qr),'\n');
	}
	return 0;
}
/*

*/

你会发现这玩意儿极其简洁。虽然说理解需要花费一段时间，但是理解了猫树的实现后，其实就很好操作了，而且常数比线段树小，时间复杂度也小。

申明一些定义：

q[][] 表示第层中所在区间的区间最大子段和；
s[][] 同理，但必须包含端点。
Lg[] 是预处理的值。

然后其它注释就在代码中了。

渡尘

那么同样的，的那道题也就可以做了（直接引用的原因我觉得那就是个板子题，虽然不是这样写的）。

有一个非常离谱的坑点在于，这道题的，输出量极大，导致一般的 write() 直接挂掉了，用了的 fwrite() 才过的。

AC Code

// Problem: C. [CSP Day7] 渡尘
// Contest: ZROI - 22csp7连 day7 之送你上路
// URL: http://zhengruioi.com/contest/1279/problem/2451
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void checkMax(T &x,T y)
{
	x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
	x=x<y?x:y;
}
const int MAXN=1e6+10,MAXM=3e6+10;
const ll INF=4e18;
namespace FIO
{
    const int L = 1 << 15;
    int l = 0;
    char buf[L | 100], out[L | 100], *S, *E;
    #define gh() (S == E ? E = (S = buf) + fread(buf, 1, L, stdin), (S == E ? EOF : *S++) : *S++)
    #define IL inline
    IL void flus(){ fwrite(out, 1, l, stdout), l = 0; }
    struct Fluser{ ~Fluser(){ flus(); } } fluser;
    IL void putc(char x)
    {
        out[l++] = x;
        if (!(l ^ L)) flus();
    }
    void read(char *s)
	{
		char ch = gh();
		while (ch < 33 || ch > 126) ch = gh();
		for (; ch >= 33 && ch <= 126; ch = gh()) *s++ = ch;
		*s = '\0';
	}
    template<typename T>
    IL void read(T &x)
    {
        char ch = gh(), t = 0;
        for (; ch < '0' || ch > '9'; ch = gh()) t |= ch == '-';
        for (x = 0; ch >= '0' && ch <= '9'; ch = gh()) x = x * 10 + (ch ^ 48);
        if (t) x = -x;
    } 
    template<typename T>
    IL void write(T x)
    {
        if (x < 0) x = -x, putc('-');
        if (x > 9) write(x / 10);
        putc(x % 10 + '0');
    }
    IL void write(const char *s){ while (*s) putc(*s++); }
    template<typename T, typename ...Args>
	void read(T &x, Args &...args){ read(x), read(args...); }
    template<typename T, typename ...Args>
	void write(T x, Args ...args){ write(x), write(args...); }
    #undef gh
    #undef IL
}
using FIO::read;
using FIO::write;
int N,Q,Len;
ll Val[MAXN],Lg[MAXN],Pos[2][MAXN],prep,sum_;
ll q[32][MAXN],s[32][MAXN];
ll t[32][MAXN],b[32][MAXN];
#define ls p<<1
#define rs p<<1|1
void buildAx(int p,int l,int r,int d)
{
	if(l==r) return Pos[0][l]=p,void();
	int mid=(l+r)>>1;
	q[d][mid]=s[d][mid]=prep=sum_=Val[mid],checkMax(sum_,0ll);
	for(int i=mid-1;i>=l;--i)
	{
		prep+=Val[i],sum_+=Val[i],s[d][i]=std::max(s[d][i+1],prep);
		q[d][i]=std::max(q[d][i+1],sum_),checkMax(sum_,0ll);
	}
	q[d][mid+1]=s[d][mid+1]=prep=sum_=Val[mid+1],checkMax(sum_,0ll);
	for(int i=mid+2;i<=r;++i)
	{
		prep+=Val[i],sum_+=Val[i],s[d][i]=std::max(s[d][i-1],prep);
		q[d][i]=std::max(q[d][i-1],sum_),checkMax(sum_,0ll);
	}
	buildAx(ls,l,mid,d+1),buildAx(rs,mid+1,r,d+1);
}
inline ll queryMax(int l,int r)
{
	if(l==r) return Val[l];
	int d=Lg[Pos[0][l]]-Lg[Pos[0][l]^Pos[0][r]];
	return std::max(std::max(q[d][l],q[d][r]),s[d][l]+s[d][r]);
}
void buildIn(int p,int l,int r,int d)
{
	if(l==r) return Pos[1][l]=p,void();
	int mid=(l+r)>>1;
	t[d][mid]=b[d][mid]=prep=sum_=Val[mid],checkMin(sum_,0ll);
	for(int i=mid-1;i>=l;--i)
	{
		prep+=Val[i],sum_+=Val[i],b[d][i]=std::min(b[d][i+1],prep);
		t[d][i]=std::min(t[d][i+1],sum_),checkMin(sum_,0ll);
	}
	t[d][mid+1]=b[d][mid+1]=prep=sum_=Val[mid+1],checkMin(sum_,0ll);
	for(int i=mid+2;i<=r;++i)
	{
		prep+=Val[i],sum_+=Val[i],b[d][i]=std::min(b[d][i-1],prep);
		t[d][i]=std::min(t[d][i-1],sum_),checkMin(sum_,0ll);
	}
	buildIn(ls,l,mid,d+1),buildIn(rs,mid+1,r,d+1);
}
inline ll queryMin(int l,int r)
{
	if(l==r) return Val[l];
	int d=Lg[Pos[1][l]]-Lg[Pos[1][l]^Pos[1][r]];
	return std::min(std::min(t[d][l],t[d][r]),b[d][l]+b[d][r]);
}
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(N,Q),Len=1;
	while(Len<N) Len<<=1;
	for(int i=1;i<=N;++i) read(Val[i]);
	for(int i=2,l=Len<<1;i<=l;++i) Lg[i]=Lg[i>>1]+1;
	buildAx(1,1,Len,1);
	buildIn(1,1,Len,1);
	for(int ql,qr;Q--;)
	{
		read(ql,qr);
		ll resax=queryMax(ql,qr),resin=queryMin(ql,qr);
		write(std::max(resax,-resin),"\n");
	}
	return 0;
}
/*

*/

GSS V

比较超纲的区间子段和，有些思维难度。需要考虑维护三个 max ，记录包含左区间，包含右区间，以及整区间的子段和，做法与类似，但是在考虑区间包含端点问题上要做一些小小的分讨。

AC Code

// Problem: SP2916 GSS5 - Can you answer these queries V
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP2916
// Memory Limit: 1500 MB
// Time Limit: 132 ms
// Written by: Eternity
const int MAXN=2e4+10;
int Test,N,Q,Val[MAXN];
struct CatTree
{
	int Len,Lg[MAXN<<1],Pos[MAXN];
	int Ln[20][MAXN],Lst[20][MAXN];
	int Rn[20][MAXN],Rst[20][MAXN];
	#define ls p<<1
	#define rs p<<1|1
	inline void init(int n)
	{
		for(Len=2;Len<N;Len<<=1);
		for(int i=1,l=Len<<1;i<=l;++i) Lg[i]=Lg[i>>1]+1;
	}
	void build(int p,int l,int r,int d)
	{
		if(l==r) return Pos[l]=p,void();
		int prep,sum_,mid=(l+r)>>1;
		Ln[d][mid]=Rn[d][mid]=Lst[d][mid]=Rst[d][mid]=prep=sum_=Val[mid],checkMax(sum_,0);
		for(int i=mid-1;i>=l;--i)
		{
			prep+=Val[i],sum_+=Val[i],Lst[d][i]=prep;
			Rn[d][i]=std::max(Rn[d][i+1],prep),Rst[d][i]=sum_;
			Ln[d][i]=std::max(Ln[d][i+1],sum_),checkMax(sum_,0);
		}
		Ln[d][mid+1]=Rn[d][mid+1]=Lst[d][mid+1]=Rst[d][mid+1]=prep=sum_=Val[mid+1],checkMax(sum_,0);
		for(int i=mid+2;i<=r;++i)
		{
			prep+=Val[i],sum_+=Val[i],Lst[d][i]=prep;
			Rn[d][i]=std::max(Rn[d][i-1],prep),Rst[d][i]=sum_;
			Ln[d][i]=std::max(Ln[d][i-1],sum_),checkMax(sum_,0);
		}
		build(ls,l,mid,d+1),build(rs,mid+1,r,d+1);
	}
	inline int query(int l,int r)
	{
		if(l>r) return 0;
		if(l==r) return Val[l];
		int d=Lg[Pos[l]]-Lg[Pos[l]^Pos[r]];
		return Lst[d][l]+Lst[d][r];
	}
	inline int queryPre(int l,int r)
	{
		if(l>r) return 0;
		if(l==r) return Val[l];
		int d=Lg[Pos[l]]-Lg[Pos[l]^Pos[r]];
		return std::max(Lst[d][l]+Rn[d][r],Rst[d][l]);
	}
	inline int querySuf(int l,int r)
	{
		if(l>r) return 0;
		if(l==r) return Val[l];
		int d=Lg[Pos[l]]-Lg[Pos[l]^Pos[r]];
		return std::max(Rst[d][r],Rn[d][l]+Lst[d][r]);
	}
	inline int queryMid(int l,int r)
	{
		if(l>r) return 0;
		if(l==r) return Val[l];
		int d=Lg[Pos[l]]-Lg[Pos[l]^Pos[r]];
		return std::max(std::max(Ln[d][l],Ln[d][r]),Rn[d][l]+Rn[d][r]);
	}
	#undef ls
	#undef rs
}Tr;
inline int querySum(int l1,int r1,int l2,int r2)
{
	int res=0;
	if(r1<l2) return Tr.query(r1+1,l2-1)+Tr.querySuf(l1,r1)+Tr.queryPre(l2,r2);
	res=l1<l2?std::max(Tr.queryMid(l2,r1),Tr.querySuf(l1,l2)+Tr.queryPre(l2,r2)-Val[l2]):Tr.queryMid(l2,r1);
	if(r2>r1) checkMax(res,Tr.querySuf(l1,r1)+Tr.queryPre(r1,r2)-Val[r1]);
	return res;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N);
		for(int i=1;i<=N;++i) read(Val[i]);
		Tr.init(N);
		Tr.build(1,1,Tr.Len,1);
		read(Q);
		for(int ll,lr,rl,rr;Q--;)
		{
			read(ll,lr,rl,rr);
			write(querySum(ll,lr,rl,rr),'\n');
		}
	}
	return 0;
}
/*

*/

带修猫树（非常规）

虽然我在前言明确说了猫树不支持修改，但事实是，猫树可以修改，比较麻烦。有一篇博客是这样写的：

对于猫树的单点修改，可以考虑修改前缀和，这样的复杂度是的，而如果我们还要修改前缀前缀和的话，把区间长度和出来，就至少是的。

然后对于猫树的区间修改的话，大概是级别的，甚至不如暴力修改。

所以可以总结为——猫树不支持修改。