喵~

猫树

你肯定想知道它为什么要叫猫树（Cat Tree），其实就像珂朵莉树（Old Driver Tree）一样，只是创造的人喜欢罢了

问题

先看猫树用来解决什么问题，一句话说，就是不带修改的线段树

线段树的时间为 $O(n) + O(\log n)$ （预处理 + 单次询问），而猫树可以做到 $O(n \log n) + O(1)$ ，但是不带修改（感觉好没用啊），一般用于优化dp之类的

思路

思路非常简单：由于不带修改，可以线段树上每一段信息统计出来，直接调用

预处理

先看预处理，类似线段树的 build ，我们用递归的方式预处理

设处理到区间 $[l, r]$ ，就维护好其信息（这个信息不同于线段树的整体，而是更细致的信息，且一般以 $mid$ 为界，比如线段树维护“区间和”，猫树这里就应统计 $[l, mid]$ 的后缀和与 $[mid + 1, r]$ 的前缀和），然后进入左右段，时空明显 $O(n \log n)$ （假设统计信息是 $O(n)$ 的）

询问

这才是精髓，看看它是如何做到 $O(1)$ 的

如果只是预处理了，它的询问还是要递归，这不还是 $O(\log n)$ ？这可不行

我们逆向思考，如果是从叶节点 $[x, x]$ 和 $[y, y]$ 向上走，那它们第一次相遇于LCA处时，对应的区间就是唯一一个满足 $l \le x \le mid \le y \le r$ 的区间，而我们在这个区间统计的信息就足以回答询问了（比如“区间和”，我们统计的前后缀足以回答 $[x, y]$ 的和）

那么问题变成树上LCA，而且是完全二叉树，倍增是 $O(\log \log n)$ ，ST表可以做到 $O(1)$ ，但如果只是这样，似乎略显麻烦，体现不出猫树的优势啊

注意到，猫树它和线段树一样，采用“父子二倍”标号，而 $(110101)_2$ 和 $(110011)_2$ 的LCA就是最长公共前缀 $(110)_2$ ，大家可以手玩验证一下

那么怎么快速求出两个数的二进制的最长公共前缀？

求法是有的，但都不是很简单（太麻烦了还不如用ST表），我们退而求其次

设两个数的二进制的最长公共前缀长度为 $len$ （二进制下），发现两个数异或之后，最高位右移了 $len$ 位，而一个数的二进制长度就是 $\log n + 1$ ，可以预处理出 $\log$ $O(1)$ 得LCA的二进制长度

那长度有啥用呢？别忘了，在“父子二倍”标号下，长度就是层数啊！我们求得了LCA在树上是第几层

那有什么用呢？别忘了我们还知道查询的端点 $x, y$ ，考虑在预处理时把同一层的信息直接存在同一个数组里，如让 sum[x][i] 代表第 $x$ 层的前缀（ $i > mid$ ）/后缀（ $i \le mid$ ）和，由于一层的节点没有重复覆盖，这是可以做到的

例题

还是给道题：GSS5

#include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 1e4 + 5, D = 18;
int log_2[N << 2], a[N], len;
struct CatTree
{
    //记录对应叶节点
    int pos[N << 1];
    
    //sum前/后缀和,mmx端点为mid最大子段和,mx最大子段和,imx端点为i的最大子段段和
    int sum[D][N << 1], mmx[D][N << 1], mx[D][N << 1], imx[D][N << 1];
    
    void build(int u, int l, int r, int d)
    {
        if (l == r)
            return pos[l] = u, void();
        int t, tt, mid = l + r >> 1;
        sum[d][mid] = mmx[d][mid] = mx[d][mid] = imx[d][mid] = t = tt = a[mid], tt = max(tt, 0);
        for (int i = mid - 1; i >= l; --i)
        {
            t += a[i], tt += a[i];
            sum[d][i] = t, imx[d][i] = tt;
            mmx[d][i] = max(mmx[d][i + 1], t);
            mx[d][i] = max(mx[d][i + 1], tt);
            tt = max(tt, 0);
        }
        sum[d][mid + 1] = mmx[d][mid + 1] = mx[d][mid + 1] = imx[d][mid + 1] = t = tt = a[mid + 1], tt = max(tt, 0);
        for (int i = mid + 2; i <= r; ++i)
        {
            t += a[i], tt += a[i];
            sum[d][i] = t, imx[d][i] = tt;
            mmx[d][i] = max(mmx[d][i - 1], t);
            mx[d][i] = max(mx[d][i - 1], tt);
            tt = max(tt, 0);
        }
        build(u << 1, l, mid, d + 1), build(u << 1 | 1, mid + 1, r, d + 1);
    }
    //typ:1sum 2pre 3suf 4mid
    int ask(int l, int r, int typ)
    {
        if (l > r)
            return 0;
        if (l == r)
            return a[l];
        int d = log_2[pos[l]] - log_2[pos[l] ^ pos[r]];
        if (typ == 1)
            return sum[d][l] + sum[d][r];
        if (typ == 2)
            return max(sum[d][l] + mmx[d][r], imx[d][l]);
        if (typ == 3)
            return max(mmx[d][l] + sum[d][r], imx[d][r]);
        return max(max(mx[d][l], mx[d][r]), mmx[d][l] + mmx[d][r]);
    }
} ct;
void prev()
{
    log_2[1] = 0;
    for (int i = 2, t = N << 2; i < t; ++i)
        log_2[i] = log_2[i >> 1] + 1;
}
int ask(int l1, int r1, int l2, int r2)
{
    
    if (r1 < l2)
        return ct.ask(l1, r1, 3) + ct.ask(r1 + 1, l2 - 1, 1) + ct.ask(l2, r2, 2);
    int res;
    res = max(ct.ask(l2, r1, 4), ct.ask(l1, l2, 3) + ct.ask(l2, r2, 2) - a[l2]);
    res = max(res, ct.ask(l1, r1, 3) + ct.ask(r1, r2, 2) - a[r1]);
    return res;
}
int main()
{
    int T, n, m, l1, r1, l2, r2;
    prev();
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        //要保证满二叉树
        for (len = 2; len < n; len <<= 1);
        ct.build(1, 1, len, 1);
        scanf("%d", &m);
        while (m--)
        {
            scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
            printf("%d\n", ask(l1, r1, l2, r2));
        }
    }
    return 0;
}