猫树

猫树是一种特殊的线段树，可以非常方便地进行一次 build 后多次区间查询无修改，实现也特别简单，不需要线段树那种复杂的函数，比 zkw 线段树都好写。

那么是如何实现的呢？

参考上图，为了方便计算，猫树需要将 $n$ 补全成为 $2^k\ge n$，并且下标从0开始。这里去掉所有的叶子节点，因为对叶子结点上的查询可以直接询问点。对于一个节点将它分成左右两半，对左边一半做后缀和，右边一半做前缀和，查询只需要找到 $l,r$ 在某个节点两边，然后合并起来就行。时间复杂度就是合并复杂度。预处理和空间复杂度都是 $\Theta(n\log n)$ 的。索要求的那个节点其实就是 $l,r$ 的 lca。怎么求呢？只需要求出 $l\oplus r$ 最高位的 1 是哪一位就知道在哪一层，然后就直接算了。具体如何操作还是看代码。

//calculate m
int m, l;
for (m = 1, l = 0; m < n; m <<= 1, ++l);
//depth from 0 to l - 1 without leaves.
type a[max_m]; //origin data
type t[max_l][max_m]; //cat tree
void build() {
  for (int i = 0; i < l; ++i) {
    for (int j = 0; j < m; j += (1 << (i + 1))) {
      t[i][j + (1 << i) - 1] = a[j + (1 << i) - 1];
      t[i][j + (1 << i)] = a[j + (1 << i)];
      for (int k = 1; k < (1 << i); ++k) {
        t[i][j + (1 << i) - 1 - k] = a[j + (1 << i) - 1 - k] + t[i][j + (1 << i) - k];
        t[i][j + (1 << i) + k] = t[i][j + (1 << i) + k - 1] + a[j + (1 << i) + k];
      }
    }
  }
}
type qur(int l, int r) {
  if (l == r) return a[l];
  int k = std::__lg(l ^ r); //You can use array to replace it. Just let lg[1]=0 and then lg[i] = lg[i / 2] + 1;
  return t[k][l] + t[k][r];
}

代码如上，build 函数就是枚举层（从下往上）然后一段一段算。查询非常简单，得到层数后相加即可。

例题

GSS1 - Can you answer these queries I

#include <bits/stdc++.h>
char buf[5000000], *p1, *p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,5000000,stdin),p1==p2)?EOF:*p1++)
#define read_s(x) do{x=0;bool f=0;int ch;while(!isdigit(ch=nc()))f|=ch=='-';do{x=x*10+(ch^48);}while(isdigit(ch=nc()));f&&(x=-x);}while(0)
void read() {};
template<typename T, typename... Args>
void read(T& x, Args& ...args) {
  read_s(x);
  read(args...);
}
#define N 65540
using blk = std::array<int, 4>; //pre, max, suffix, sum
int n, m, x;
blk a[N];
blk t[16][N];
int q, l, r;
blk operator+ (const blk& a, const blk& b) {
  blk res{};
  res[0] = std::max(a[0], a[3] + b[0]);
  res[1] = std::max({a[1], b[1], a[2] + b[0]});
  res[2] = std::max(a[2] + b[3], b[2]);
  res[3] = a[3] + b[3];
  return res;
}
void build() {
  for (int i = 0; i < x; ++i) {
    for (int j = 0; j < m; j += (1 << (i + 1))) {
      t[i][j + (1 << i) - 1] = a[j + (1 << i) - 1];
      t[i][j + (1 << i)] = a[j + (1 << i)];
      for (int k = 1; k < (1 << i); ++k) {
        t[i][j + (1 << i) - 1 - k] = a[j + (1 << i) - 1 - k] + t[i][j + (1 << i) - k];
        t[i][j + (1 << i) + k] = t[i][j + (1 << i) + k - 1] + a[j + (1 << i) + k];
      }
    }
  }
}
blk qur(int l, int r) {
  if (l == r) return a[l];
  int k = std::__lg(l ^ r); //You can use array to replace it. Just let lg[1]=0 and then lg[i] = lg[i / 2] + 1;
  return t[k][l] + t[k][r];
}
int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  read(n);
  for (int i = 0; i < n; ++i) read(a[i][0]), a[i][1] = a[i][2] = a[i][3] = a[i][0];
  for (m = 1, x = 0; m < n; m <<= 1, ++x);
  build();
  read(q);
  while (q--) {
    read(l, r);
    --l, --r;
    auto res = qur(l, r);
    std::cout << res[1] << '\n';
  }
  return 0;
}

猫树拓展

猫树也可以在一些 CDQ 分治中起到优化复杂度的作用。观察到猫树的遍历和 CDQ 分治的顺序可以说一模一样，所以可以优化下面这类 CDQ 问题。在左区间对右区间更新时，出现如下情况：

• 左区间一个点对右区间一个区间进行区间操作。
• 右区间一个点对左区间一个区间进行查询操作。

对于这种我们可以这样操作，对于修改，我们可以直接找到 $l,r$ 的那一层然后对两个点打一个标记，容易发现层一定是在当前层之下的。

对于查询操作，就和标准的查询一样。当我们进入一个 $\textrm{solve}(l,r)$ 的时候，就更新一下上面对这一层左半边和右半边的操作，就和 build 的方向相反，左半边求前缀和，右半边后缀和即可，然后枚举的时候同时也要对原本的序列进行更新。当我们递归到单个节点时，就能求出我们想要的答案了，这个时候我们又要用这个答案去更新我们要查询的序列中的值。在一个节点内 $\textrm{solve}(l,mid)$ 和 $\textrm{solve}(mid+1,r)$ 后，对当前节点左半边和右半边进行更新，这里的操作就和普通的 build 一样了。

这样的操作就可以吧两个 $\log$ 的操作优化到一个 $\log$，非常巧妙。这样操作等价于修改的区间每次下传，当每一层有的区间要裂开，就分成左半边和右半边分别处理，感觉有点类似于线段树分治？然后上传的时候就是相当于普通的猫树了。