首页 > 分享 > 数据结构入门——猫树

数据结构入门——猫树

萌宠菠菠乐园
2024-10-27 09:06

数据结构入门——猫树

1 简介#

线段树的一种扩展，静态查询可以做到 O(nlog⁡n)" role="presentation">O(nlog⁡n) 的预处理，O(1)" role="presentation">O(1) 的查询，但是不能扩展，只能解决特定问题，因此并不常用。

2 算法简介#

猫树是一个线段树的结构，处理每一层的信息我们然后我们向下递归的去处理。

为了方便查询，我们把序列长度扩展到 2" role="presentation">2 的幂，然后按照线段树的结构去建整颗树，左右端点的编号分别为 2k,2k+1" role="presentation">2k,2k+1 ，考虑分治，我们可以用 O(nlog⁡n)" role="presentation">O(nlog⁡n) 的时间复杂度预处理全部的信息。

信息的维护因题而异，下面讲一下如何做到 O(1)" role="presentation">O(1) 查询。

因为我们已经将序列长度扩展到 2" role="presentation">2 的幂，所以不难发现整棵树有以下性质：

每一个节点的二进制长度就是他所在猫树的层数。（根节点在第一层）两个节点的 lca 是他们编号二进制的 lcp。

当然我们只需要知道他们的 lca 在哪一层上就可以了。

实际上，如果设两个节点是 a,b" role="presentation">a,b ，数 x" role="presentation">x 的二进制长度为 lgx" role="presentation">lgx，那么他们 lca 所在层数为 lga−lga^b" role="presentation">lga−lga^b。

3 例题#

最大字段和

把区间扩充到 2" role="presentation">2 的幂：

while(len<n) len<<=1;

预处理每个数二进制的长度：

for(int i=1;i<=len<<1;i++) lg[i]=lg[i>>1]+1;

注意，序列长度为 len" role="presentation">len 时，最大节点编号可以达到 2×len" role="presentation">2×len 的级别。

建树：

inline void build(int k,int l,int r,int deep){ if(l==r){ id[l]=k; return; } int mid=l+r>>1,sum2=a[mid],sum1=a[mid]<0?0:a[mid]; f[mid][deep]=a[mid];g[mid][deep]=a[mid]; for(int i=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]<0?0:a[mid+1]; f[mid+1][deep]=a[mid+1];g[mid+1][deep]=a[mid+1]; for(int i=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); }

注意，我们没有必要把整颗树建出来，就是我们不用维护节点之间的父子关系，我们只需要维护该节点所代表的区间的信息就可以。

fi,d" role="presentation">fi,d 表示：如果 i>mid" role="presentation">i>mid ，那么指的就是 [mid+1,i]" role="presentation">[mid+1,i] 这段区间的最大子段和，否则指的是 [i,mid]" role="presentation">[i,mid] 这段区间的最大字段和。

gi,d" role="presentation">gi,d 表示：如果 i>mid" role="presentation">i>mid ，那么指的就是区间 [mid+1,i]" role="presentation">[mid+1,i] 强制左端点在 mid+1" role="presentation">mid+1 的子段的最大子段和。否则指的是区间 [i,mid]" role="presentation">[i,mid] 强制右端点在 mid" role="presentation">mid 的子段的最大字段和，dp 转移就可以。

在 dp 的时候注意 f,g,sum1,sum2" role="presentation">f,g,sum1,sum2 的预处理，在这里挂掉了好几次。

注意，因为我们是在树上查询，我们需要知道序列上每一个点对应的节点是多少。

查询代码：

inline int query(int l,int r){ if(l==r) return a[l]; int d=lg[id[l]]-lg[id[l]^id[r]]; return Max(Max(f[l][d],f[r][d]),g[l][d]+g[r][d]); }

这个比较显然。

完整代码：

#include<bits/stdc++.h> #define dd double #define ld long double #define ll long long #define int long long #define uint unsigned int #define ull unsigned long long #define N 1000000 #define M number using namespace std; const int INF=0x3f3f3f3f; inline int Max(int a,int b){ return a>b?a:b; } template<typename T> inline void read(T &x) { x=0; int f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c == '-') f=-f; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; x*=f; } int n,len=1,lg[N],f[N][30],g[N][30],id[N],a[N],m; inline void build(int k,int l,int r,int deep){ if(l==r){ id[l]=k; return; } int mid=l+r>>1,sum2=a[mid],sum1=a[mid]<0?0:a[mid]; f[mid][deep]=a[mid];g[mid][deep]=a[mid]; for(int i=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]<0?0:a[mid+1]; f[mid+1][deep]=a[mid+1];g[mid+1][deep]=a[mid+1]; for(int i=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); } inline int query(int l,int r){ if(l==r) return a[l]; int d=lg[id[l]]-lg[id[l]^id[r]]; return Max(Max(f[l][d],f[r][d]),g[l][d]+g[r][d]); } signed main(){ read(n); while(len<n) len<<=1; for(int i=1;i<=len<<1;i++) lg[i]=lg[i>>1]+1; for(int i=1;i<=n;i++){ read(a[i]); } build(1,1,len,1); read(m); for(int i=1;i<=m;i++){ int l,r;read(l);read(r); printf("%lldn",query(l,r)); } return 0; }