猫树分治，又称二区间合并，一种可以用 \(O(n\log n)\) 时空复杂度预处理，\(O(1)\) 处理区间询问的算法，与 cdq 和整体二分类似。
我们考虑线段树上，我们通过 pushup 操作不断合并两个区间，做到查询 \(O(\log n)\) 个区间回答询问，但是如果没有修改操作，我们可以只询问 \(O(1)\) 个区间来回答询问。
即，我们需要找到一个区间，使得其包含我们整个询问区间，且中点落在询问区间内。考虑堆式建树，\(i\) 的左儿子是 \(2i\)，右儿子是 \(2i+1\)，那么显然我们要找到的是 \([l,l]\) 和 \([r,r]\) 在树上的 \(\text{LCA}\)，而如何求出 \(\text{LCA}\) 呢。
因为采用了堆式建树，记 \([l,l]\) 编号为 \(x\)，\([r,r]\) 编号为 \(y\)，那么其 \(LCA\) 编号为 x >> log[x^y]，此处 log 数组的定义在 \(1\) 处为 \(1\)。
其实，在可以离线的问题中我们完全可以类似整体二分，将询问不断分组来找中点也可以。
之后，我们找到了这个大区间，那么我们其实只要预处理出从区间中点出发向左向右的前后缀答案，再做拼接即可，这也要求问题需要有可加性，比如区间最大子段和，\(\{\max,+\}\) 卷积之类的。
P6240 好吃的题目
给定价值和代价序列，\(q\) 次询问，给定
l r t,查询区间 01 背包上限为 \(t\) 的答案。
\(1 \le n \le 4\times 10^4\),\(1 \le q \le 2\times 10^5,1 \le h_i,t \le 200,1\le w_i \le 10^7\)。
发现 01 背包形如 \(\max \{ f_i + f_{t-i}\}\)，即 \(\{\max,+\}\) 卷积，满足区间可加性，直接猫树分治，每次对 \((mid,r]\) 处理前缀背包答案，\([l,mid]\) 处理后缀背包答案，查询时 \(O(t)\) 将两侧背包答案拼接即可。
总复杂度 \(O(nt\log n + qt)\)，跑到了最优解第一页。
const ll N=4e4+5,M=205,T=2e5+5;
ll n,m,h[N],w[N],f[N][M],ans[T],l,r,t,V;vector<tuple<ll,ll,ll,ll>> Q;
inline void solve(ll l,ll r,vector<tuple<ll,ll,ll,ll>> &Q)
{if(!Q.size()) return;ll mid=l+r>>1;fo(0,j,V) f[mid][j]=0;fo(mid+1,i,r){fo(0,j,h[i]-1) f[i][j]=f[i-1][j];fo(h[i],j,V) f[i][j]=max(f[i-1][j],f[i-1][j-h[i]]+w[i]);} fo(h[mid],j,V) f[mid][j]=w[mid];Fo(mid-1,i,l){fo(0,j,h[i]-1) f[i][j]=f[i+1][j];fo(h[i],j,V) f[i][j]=max(f[i+1][j],f[i+1][j-h[i]]+w[i]);}vector<tuple<ll,ll,ll,ll>> A,B;for(auto [l,r,lim,id]:Q){if(r<=mid) A.pb({l,r,lim,id});else if(l>mid) B.pb({l,r,lim,id});else fo(0,i,lim) ckmx(ans[id],f[l][i]+f[r][lim-i]);}Q.clear(),solve(l,mid,A),solve(mid+1,r,B);
}
signed main(){read(n,m);fo(1,i,n) read(h[i]);fo(1,i,n) read(w[i]);fo(1,i,m){read(l,r,t);if(l==r) ans[i]=(t>=h[l]?w[l]:0ll);else ckmx(V,t),Q.pb({l,r,t,i});}solve(1,n,Q);fo(1,i,m) wr(ans[i]),pr;return 0;
}