貓樹是一個(gè)有趣的數(shù)據(jù)結(jié)構(gòu)，之前一直覺得這玩意兒應(yīng)該很玄學(xué)，但學(xué)了之后發(fā)現(xiàn)還是挺樸素也挺好打的數(shù)據(jù)結(jié)構(gòu)

→o→騙訪客量

一、貓樹的作用

學(xué)一個(gè)算法當(dāng)然得先了解它的用處，那么貓樹的作用嘛…

簡單來講，線段樹能維護(hù)的信息貓樹基本都能維護(hù)

比如什么區(qū)間和、區(qū)間 gcd 、最大子段和 等 滿足結(jié)合律且支持快速合并的信息

二、貓樹的算法實(shí)現(xiàn)

什么都別說，我知道你想先知道貓樹是怎么實(shí)現(xiàn)的

我們就以區(qū)間和查詢?yōu)槔?，假設(shè)當(dāng)前查詢的區(qū)間為 [~l~,~r~]

那么如果我們在此之前預(yù)處理過某兩個(gè)區(qū)間的信息，且這兩個(gè)區(qū)間可以合并成當(dāng)前查詢區(qū)間，是不是就可以 O(1) 得到答案了呢？

但是問題就在于如何在一個(gè)較短的時(shí)間內(nèi)預(yù)處理區(qū)間信息，并且使得任意一個(gè)區(qū)間都能被分成兩份預(yù)處理過的區(qū)間

不扯了，進(jìn)入正題

1.首先將 1~n 整個(gè)區(qū)間分成兩份 1~mid ， mid+1~n

2.然后對于這兩個(gè)區(qū)間，我們先從中間點(diǎn) mid 和 mid+1 出發(fā)，O(n) 地向兩邊遍歷區(qū)間中的每個(gè)元素，同時(shí)維護(hù)要處理的信息

FAQ:怎么維護(hù)？

這得看你要維護(hù)的信息，比如我們舉例是區(qū)間和，那么處理方式如下：

對于左邊的區(qū)間，i 倒序遍歷， f[i]=f[i+1]+a[i]

對于右邊的區(qū)間，i 正序遍歷， f[i]=f[i-1]+a[i]

3.等兩個(gè)區(qū)間都處理完之后，我們再將兩個(gè)區(qū)間繼續(xù)分下去，重復(fù)迭代以上步驟直到區(qū)間左右邊界重合（即 l = r）

接著我們考慮到這樣的迭代總共會(huì)有 logn 層，一個(gè)數(shù)都會(huì)在每一層中都被計(jì)算到一次，也就是說時(shí)間復(fù)雜度是 nlogn 的，雖然比不上線段樹預(yù)處理的線性復(fù)雜度，但也已經(jīng)能夠讓人接受了

至于空間方面，我們考慮向下迭代的長度相同的區(qū)間兩兩不相交，那么他們其實(shí)可以存在同一維數(shù)組里面，也就是說我們的空間復(fù)雜度也是 nlogn 的，在承受范圍之內(nèi)

但是這里還有一個(gè)問題：如何保證每個(gè)區(qū)間都能被分成兩份預(yù)處理過的區(qū)間？

其實(shí)我們看到上面的處理方法使得

某個(gè)預(yù)處理過的區(qū)間 可以將任意一個(gè)左右端點(diǎn)都在該區(qū)間內(nèi)，且經(jīng)過該區(qū)間中點(diǎn)的區(qū)間分成兩份，而這兩份區(qū)間已經(jīng)處理過了，那么就可以 O(1) 合并求解了

可能你已經(jīng)玄學(xué)理解了，但是用圖還是證明一下好了

Proof：

還是畫圖好…下面是一個(gè)不斷向下迭代的區(qū)間

我們先將查詢區(qū)間的兩個(gè)端點(diǎn)表示在總區(qū)間上

我們發(fā)現(xiàn)這兩個(gè)點(diǎn)并不能被當(dāng)前所在區(qū)間的中間點(diǎn)分到兩邊，于是我們將他們下移，那么這兩個(gè)點(diǎn)就一起進(jìn)入了右區(qū)間

我們發(fā)現(xiàn)還是他們還是不能被中間點(diǎn)分成兩份，繼續(xù)下移，一起進(jìn)入左區(qū)間

可以被分成兩份了，那么我們就成功地將該詢問區(qū)間分成了兩個(gè)已處理的區(qū)間

根本原因我已經(jīng)在上面加粗了，沒錯(cuò)，就是一起，如果兩個(gè)點(diǎn)無法被當(dāng)前所處區(qū)間分到中間點(diǎn)的兩邊，那么他們必然在該區(qū)間的左半部分或者右半部分，那么就可以同時(shí)進(jìn)入某一邊的區(qū)間了

于是乎得證了…

三、貓樹的復(fù)雜度分析

然后，算法的復(fù)雜度總得分析的吧…

預(yù)處理復(fù)雜度

其實(shí)這個(gè)東西上面講過了，就是 O(nlogn) ， 漏看的同學(xué)可以翻回去了

詢問復(fù)雜度

我們發(fā)現(xiàn)上面的預(yù)處理方式已經(jīng)滿足了我們分割區(qū)間的要求，但是…

FAQ:按照上面的找尋分割點(diǎn)的方法，我們發(fā)現(xiàn)復(fù)雜度好像是 O(logn)的？ （這不還是線段樹的復(fù)雜度？）

別急，上面只是證明分割的可行性，并不是找尋分割點(diǎn)的方法

其實(shí)不難看出，如果我們讓兩個(gè)點(diǎn)從葉子結(jié)點(diǎn)出發(fā)，不斷向上走知道相遇，那么該區(qū)間的中間點(diǎn)就是它們的分割點(diǎn)。

emmm…兩個(gè)節(jié)點(diǎn)不斷向上走？這不是 LCA 嘛！那我們就用倍增或者樹剖來找LCA ？

然后我們會(huì)發(fā)現(xiàn)查詢復(fù)雜度神奇地變成了 O(loglogn)，已經(jīng)比線段樹強(qiáng)了哈？

還不夠優(yōu)秀？對，還可以繼續(xù)優(yōu)化

之前我們有提到分割點(diǎn)在 LCA 上，那我們可以 O(1) 得到兩個(gè)節(jié)點(diǎn)的 LCA 么？ST表？貌似是可以的哦，但其實(shí)不用這么麻煩

我們觀察一下就可以發(fā)現(xiàn)（或者說根據(jù)線段樹的性質(zhì)來說），兩個(gè)葉子結(jié)點(diǎn)的 LCA 的節(jié)點(diǎn)編號其實(shí)就是他們編號的最長公共前綴（二進(jìn)制下）

Eg：

編號為 (10001)_2 和 (10110)_2 的兩個(gè)節(jié)點(diǎn)的 LCA 編號就是 (10)_2

那么怎么快速求出兩個(gè)數(shù)的最長公共前綴？

這里要用到非常妙的一個(gè)辦法：

我們將兩個(gè)數(shù)異或之后可以發(fā)現(xiàn)他們的公共前綴不見了，即最高位的位置后移了 logLCA.len ， 其中 LCA.len 表示 LCA 節(jié)點(diǎn)在二進(jìn)制下的長度

那么我們就可以預(yù)處理一下 log 數(shù)組，然后在詢問的時(shí)候就可以快速求出兩個(gè)詢問節(jié)點(diǎn)的 LCA 所在的 層 了

等等，層？不用求出編號的么？

那么上面又說過的啊…我們將長度相同的區(qū)間放在一維數(shù)組里了啊，那么我們又知道這兩個(gè)區(qū)間的左右邊界，中間點(diǎn)又是確定的，當(dāng)然可以在該層中得到我們想要的信息并快速合并起來了（這個(gè)的話還是得看代碼理解的吧？）

綜上所述，我們可以在 O(1) 的時(shí)間復(fù)雜度內(nèi)查詢區(qū)間

這復(fù)雜度比起線段樹都差一個(gè) log 了，一般來講就是十幾倍的時(shí)間，然鵝自己造了數(shù)據(jù)測了測發(fā)現(xiàn)兩者運(yùn)行時(shí)間僅為兩三倍，究其原因的話還是普通線段樹的 log 基本是跑不滿的（換句話說，我數(shù)據(jù)造太爛了…）

修改復(fù)雜度

修改？貓樹一般不拿來修改！

而且也有大佬向我提議說修改沒什么用，但我覺得還是講講（限制過大，僅供娛樂）

舉個(gè)例子：有些題目比較毒瘤，可能會(huì)給你的操作中大多是查詢，少數(shù)是單點(diǎn)修改

那么完蛋了，貓樹能支持修改么？果斷棄坑

其實(shí)…貓樹可以支持吧…

我們在處理的時(shí)候用的是一個(gè)類似于前綴和的做法，那么前綴和修改的復(fù)雜度是多少？（好吧一般來講帶修改就不用前綴和了，這里只是舉個(gè)例子）， O(n) ！

那么我們看看一個(gè)數(shù)在長度為 n/2 、 n/4 、 n/8 …. 1 的區(qū)間內(nèi)被做過前綴和，那么修改的時(shí)候也就是要修改這些區(qū)間，然后這些區(qū)間長度加起來…就是 n 吧？

然鵝具體的代碼實(shí)現(xiàn)就不給出了，因?yàn)槲覒?nbsp;就在這里給個(gè)思想，僅供娛樂

但是上面講的是單點(diǎn)修改，區(qū)間修改呢？

這個(gè)我真不會(huì)，而且也辦不到的…講道理改一次是 O(nlogn) 的吧（相當(dāng)于重建了），畢竟這也是性質(zhì)決定的 （區(qū)間修改想都別想趕緊棄坑）

四、貓樹的代碼實(shí)現(xiàn)

以處理區(qū)間最大子段和為例：

碼量其實(shí)會(huì)少很多，可以看到最主要的碼量就在 build 里面，但是 build 函數(shù)的思路還是很清晰的

五、貓樹的推薦例題

GSS1

就是上面的板子

GSS5

不帶修改好開森，這題要求最大前綴 、 最大后綴，但是并不影響貓樹的發(fā)揮

用了貓樹之后直接 0 ms

FAQ：貌似不用也可以啊…

但是貓樹碼量小吧…

FAQ：不見得啊….

…

下面是代碼（不壓行的代碼真心打不來）

//by Judge
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int M=2e4+3;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline void cmax(int& a,int b){if(a<b)a=b;}
inline void cmin(int& a,int b){if(a>b)a=b;}
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x,char chr='\n'){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} int n,m,a[M];
namespace cat_tree{
    int len,lg[M<<1],pos[M];
    int p[16][M],s[16][M],f[16][M],g[16][M];
    #define ls k<<1
    #define rs k<<1|1
    #define mid (l+r>>1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    inline int Max(int a,int b){return a>b?a:b;}
    inline void init(){
        for(len=2;len<n;len<<=1);
        int l=len<<1;
        for(int i=1;i<=l;++i)
            lg[i]=lg[i>>1]+1;
    }
    void build(int k,int l,int r,int d){
        if(l==r) return pos[l]=k,void();
        int prep,sm;
        f[d][mid]=g[d][mid]=a[mid];
        p[d][mid]=s[d][mid]=a[mid];
        prep=sm=a[mid],sm=Max(sm,0);
        for(int i=mid-1;i>=l;--i){
            prep+=a[i],sm+=a[i],s[d][i]=prep,
            f[d][i]=Max(f[d][i+1],prep),g[d][i]=sm,
            p[d][i]=Max(p[d][i+1],sm),sm=Max(sm,0);
        }

        f[d][mid+1]=g[d][mid+1]=a[mid+1];
        p[d][mid+1]=s[d][mid+1]=a[mid+1];
        prep=sm=a[mid+1],sm=Max(sm,0);
        for(int i=mid+2;i<=r;++i){
            prep+=a[i],sm+=a[i],s[d][i]=prep,
            f[d][i]=Max(f[d][i-1],prep),g[d][i]=sm,
            p[d][i]=Max(p[d][i-1],sm),sm=Max(sm,0);
        }
        build(lson,d+1),build(rson,d+1);
    }
    inline int query_sum(int l,int r){
        if(l>r) return 0;
        if(l==r) return a[l];
        int d=lg[pos[l]]-lg[pos[l]^pos[r]];
        return s[d][l]+s[d][r];
    }
    inline int query_pre(int l,int r){
        if(l>r) return 0;
        if(l==r) return a[l];
        int d=lg[pos[l]]-lg[pos[l]^pos[r]];
        return Max(s[d][l]+f[d][r],g[d][l]);
    }
    inline int query_suf(int l,int r){
        if(l>r) return 0;
        if(l==r) return a[l];
        int d=lg[pos[l]]-lg[pos[l]^pos[r]];
        return Max(g[d][r],f[d][l]+s[d][r]);
    }
    inline int query_mid(int l,int r){
        if(l>r) return 0;
        if(l==r) return a[l];
        int d=lg[pos[l]]-lg[pos[l]^pos[r]];
        return Max(Max(p[d][l],p[d][r]),f[d][l]+f[d][r]);
    }
} using namespace cat_tree;
inline int query(int l1,int r1,int l2,int r2){
    int ans;
    if(r1<l2) return query_sum(r1+1,l2-1)+query_suf(l1,r1)+query_pre(l2,r2);
    ans=query_mid(l2,r1);
    if(l1<l2) ans=Max(ans,query_suf(l1,l2)+query_pre(l2,r2)-a[l2]);
    if(r2>r1) ans=Max(ans,query_suf(l1,r1)+query_pre(r1,r2)-a[r1]);
    return ans;
}
int main(){
    for(int T=read();T;--T){
        n=read();
        for(int i=1;i<=n;++i)
            a[i]=read();
        init(),build(1,1,len,1);
        int l1,r1,l2,r2;
        for(int m=read();m;--m){
            l1=read(),r1=read(),
            l2=read(),r2=read(),
            print(query(l1,r1,l2,r2));
        }
    } return Ot(),0;
}