首页 > 分享 > 数据结构猫树

数据结构猫树

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

orz 算法创造者 immortalCO
orz 讲解得很好的大佬

猫树的特征:
猫树，可以高效处理维护无修改的某种支持结合律和快速合并的信息。
猫树是线段树的一个变种，其询问的时间复杂度可以达到O(1)
猫树的具体实现方式:
以区间最大和为例,如图是一个倒着的以线段形式呈现的一个线段树，从下往上分为4层，一共有8个数，这些数有正有负
请添加图片描述
当我们想要问询区间最大子段和，例如我们问询区间3到7的最大子段和，
这个问询落在区间上就是图中绿色的部分：

将这个区间问询传递一直向下传递(图中的下方)直到两者相遇(如图所示)，请添加图片描述令mid是第二层的分割点，mid=(1+8)/2=4;这时问询区间就被mid分成了两段区间最大和的位置就有以下三种可能：位于左区间，位于右区间，横跨两个区间。
所以答案就是这三种情况取最大值
而猫树之所以可以实现O(1)查询，就是因为在建树时将每一层中的每个小段中，以mid为中心分别计算两端的区间最大子段和和包含端点的最大子段和当我们查询时输入L和R，获取这个区间第一次被mid分成两段时所在的层数，再计算三种情况中的大值。
如何根据L，R获取层数：
如果我们把问询的两个点从叶子节点往下落，直到相遇，相遇所在的地方就是他们所在的层数
这就很像LCA(最近公共祖先)问题了
如果真要用常规的LCA来算层数复杂度就很高
但二叉树有一个特殊的性质
如图，给一个普通线段树每个节点加上一个编号
请添加图片描述
接着将编号转化成二进制形式

通过观察可知，两个叶子节点编号的公共前缀就是其最近公共祖先的编号

如何根据LCA的编号获取其所在的层数：
当我们以这个代码带构建以2为底的log函数

for (int i = 2; i <= n*2; ++i)//log函数lg[i] = lg[i >> 1] + 1; 12

当我们输出前10位时，就会出现以下结果
请添加图片描述
通过观察并结合上面线段树的图可知，
lg[1]=0
lg[2]=1 lg[3]=1
lg]4]=2 lg[5]=2 lg[6]=2 lg[7]=2 lg[8]=2
lg[9]=3 lg[10]=3……
i代表线段树的编号，lg[i]代表其所在的层数
由此，根据子节点编号计算LCA所在的层数的思路就清晰了
以下是代码，看十遍不如敲一遍，敲一遍代码看一遍博客，一遍不行来十遍就能理解了。就算看不懂也背过了

#include <cstdio> #include <cstring> #include <iostream> #define ll long long using namespace std; const int M = 2e5 + 3; int n, m, len, a[M]; int lg[M << 2], pos[M], p[21][M], s[21][M]; // p 数组为区间最大子段和， s 数组为包含端点的最大子段和 // 深度 void build(int u, int l, int r, int dep) { //这里的边界是叶子结点//到达叶子后要记录一下位置 l 对应的叶子结点编号if (l == r) {pos[l] = u;return ;}// 处理左半部分int mid = l + r >> 1;int prep = a[mid];int sm = a[mid];p[dep][mid] = a[mid];// p 数组为区间最大子段和，对应preps[dep][mid] = a[mid];//s 数组为包含端点的最大子段和,对应smsm = max(sm, 0);//如果端点为负数，不选端点是明智之选for (int i = mid - 1; i >= l; --i) {prep += a[i], sm += a[i];s[dep][i] = max(s[dep][i + 1], prep);//prep是全选的情况,s[dep][i+1]会"停留"在当前最优的情况p[dep][i] = max(p[dep][i + 1], sm);sm = max(sm, 0);//ms要保证不为负，如果为负，就说明前面部分不选}// 处理右半部分p[dep][mid + 1] = a[mid + 1];s[dep][mid + 1] = a[mid + 1];prep = sm = a[mid + 1];sm = max(sm, 0);for (int i = mid + 2; i <= r; i++) {prep += a[i], sm += a[i];s[dep][i] = max(s[dep][i - 1], prep);p[dep][i] = max(p[dep][i - 1], sm);sm = max(sm, 0);}build(u << 1, l, mid, dep + 1); //向下递归build(u << 1 | 1, mid + 1, r, dep + 1); } int query(int l, int r) {if (l == r)return a[l];int d = lg[pos[l]] - lg[pos[l] ^ pos[r]]; //得到 lca 所在层//pos[l] ^ pos[r]会将L和R的最近公共前缀消除掉return max(max(p[d][l], p[d][r]), s[d][l] + s[d][r]);//两种情况 1:最大区间和横跨两区间 2：在其中一个区间里//p 数组为区间最大子段和//s 数组为包含端点的最大子段和 } int main() {cin >> n;len = 2;while (len < n) {len <<= 1;}for (int i = 1; i <= n; ++i) {cin >> a[i];}int l = len << 1;//右区间乘二for (int i = 2; i <= l; ++i)//log函数lg[i] = lg[i >> 1] + 1;build(1, 1, len, 1);int m;cin >> m;for (int l, r; m; m--) {cin >> l >> r;cout << query(l, r) << endl;}return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192

吐槽一下痛苦的学习经历，之前我看的那个讲猫树的博客里的代码有令人费解的宏定义，毫无头绪的函数，阴间的压行。看代码之前都要把代码翻译成朴素的语言才能看，博客写来是给别人看的啊喂QWQ