线段树的一种扩展，静态查询可以做到\(O(n\logn)\)的预处理，\(O(1)\)的查询，但是不能扩展，只能解决特定问题，因此并不常用。
猫树是一个线段树的结构，处理每一层的信息我们然后我们向下递归的去处理。
信息的维护因题而异，下面讲一下如何做到\(O(1)\)查询。
因为我们已经将序列长度扩展到\(2\)的幂，所以不难发现整棵树有以下性质：
当然我们只需要知道他们的lca在哪一层上就可以了。
实际上，如果设两个节点是\(a,b\)，数\(x\)的二进制长度为\(lg_x\)，那么他们lca所在层数为\(lg_a-lg_{a\hat{}b}\)。
把区间扩充到\(2\)的幂：
while(len for(inti=1;i<=len<<1;i++)lg[i]=lg[i>>1]+1;注意，序列长度为\(len\)时，最大节点编号可以达到\(2\timeslen\)的级别。 建树： inlinevoidbuild(intk,intl,intr,intdeep){if(l==r){id[l]=k;return;}intmid=l+r>>1,sum2=a[mid],sum1=a[mid]<00:a[mid];f[mid][deep]=a[mid];g[mid][deep]=a[mid];for(inti=mid-1;i>=l;i--){sum1=sum1+a[i];sum2+=a[i];f[i][deep]=Max(f[i+1][deep],sum1);g[i][deep]=Max(g[i+1][deep],sum2);if(sum1<0)sum1=0;}sum2=a[mid+1];sum1=a[mid+1]<00:a[mid+1];f[mid+1][deep]=a[mid+1];g[mid+1][deep]=a[mid+1];for(inti=mid+2;i<=r;i++){sum1=sum1+a[i];sum2+=a[i];f[i][deep]=Max(f[i-1][deep],sum1);g[i][deep]=Max(g[i-1][deep],sum2);if(sum1<0)sum1=0;}build(k<<1,l,mid,deep+1);build(k<<1|1,mid+1,r,deep+1);}注意，我们没有必要把整颗树建出来，就是我们不用维护节点之间的父子关系，我们只需要维护该节点所代表的区间的信息就可以。 \(f_{i,d}\)表示：如果\(i>mid\)，那么指的就是\([mid+1,i]\)这段区间的最大子段和，否则指的是\([i,mid]\)这段区间的最大字段和。 \(g_{i,d}\)表示：如果\(i>mid\)，那么指的就是区间\([mid+1,i]\)强制左端点在\(mid+1\)的子段的最大子段和。否则指的是区间\([i,mid]\)强制右端点在\(mid\)的子段的最大字段和，dp转移就可以。 在dp的时候注意\(f,g,sum_1,sum_2\)的预处理，在这里挂掉了好几次。 注意，因为我们是在树上查询，我们需要知道序列上每一个点对应的节点是多少。 查询代码： inlineintquery(intl,intr){if(l==r)returna[l];intd=lg[id[l]]-lg[id[l]^id[r]];returnMax(Max(f[l][d],f[r][d]),g[l][d]+g[r][d]);}