一种基于根号重构实现类似平衡树的功能的方法
k_mod_zero · · 算法·理论
声明:该设想可能已经被其他人提出过,若有类似文章,麻烦联系我。
首先看一下这道题:一道平衡树的板子题。
可以看到,因为数据存在加强,所以无法通过离散化来规避,必须动态维护所有数字,而 std::set 等数据结构虽然能够直接使用,但显然无法维护题目所给的排名、前驱和后继等乱七八糟的信息,直接维护有序数组的话(a.k.a. 排序向量树),插入删除又是个灾难。所以我们必须手写平衡树或者跳表……吗?当然不是!
根号重构
根号重构可以用较为简单的方法维护集合。
很显然,我们在维护有序数组时,可以不用每次都将
那我们具体该怎么做呢
预处理
我们先定义以下常量。
typedef long long ll;
const ll BLK = 2400, INF = 0x3f3f3f3f3f3f;
// BLK 为重构阈值,INF 为无限大(其实只用比值域大)。
// read() 函数为自行编写的快速读入,其返回一个 long long
我们使用 vector 定义 3 个数组,一个大数组,两个小数组。首先,我们将大数组填上初始值并排序,在之后的操作中,我们要保证这 3 个数组都是有序的,其中,大数组和第一个小数组是我们要加入的数,第二个小数组则是我们要删除的数。
代码如下↓
vector<ll> l1, l2, l3;
// l1 (大数组)存储集合中的数
// l2 (第一个小数组)数组暂时存储要加入的数
// l3 (第二个小数组)数组暂时存储要删除的数
fff(i, 1, n){
ll x = read();
l1.push_back(x);
}
sort(l1.begin(), l1.end());
// 读入并排序以维护有序性
插入 / 删除
我们将该元素插入到第一个小数组中,而在删除元素时,我们将该元素插入到第二个小数组中(而不是尝试删除这个数,因为该数可能在大数组中,而对其操作非常浪费时间),我们可以使用二分查找插入位置来提升效率。
代码如下↓
// 插入元素
l2.insert(lower_bound(l2.begin(), l2.end(), x), x);
// 删除元素
l3.insert(lower_bound(l3.begin(), l3.end(), x), x);
// 两个代码意思相近,都是往数组中加入 x 并维护有序性
// lower_bound 查找插入位置,insert 插入 x
// 因为数组原本有序,可以看成是插入排序的单次操作
// 故单次时间复杂度为 O(T)
查询
看起来需要我们实现的操作非常多,但其实我们只需要实现“查询一个数的排名”的功能,就可以基于此实现一些平衡树支持的其他功能,所以让我们一个一个来。
因为查询 lower_bound 求出第一个大于等于
代码如下↓
ll rnk(ll x){
ll res = 0;
res += lower_bound(l1.begin(), l1.end(), x) - l1.begin();
res += lower_bound(l2.begin(), l2.end(), x) - l2.begin();
// l1 l2 表示加入的数
// 找到其中小于 x 的数的个数并相加
res -= lower_bound(l3.begin(), l3.end(), x) - l3.begin();
// l3 表示要删除的数
// 这些数在 l1 或 l2 中存在,但我们应该删除它
// 所以减去这些数对答案的贡献
return res + 1;
// 题目定义比 x 小的数 +1 即为排名
}
对于查询排名为
代码如下↓
ll at(ll x){
ll l = -INF, r = INF;
while(l + 1 < r){
ll m = (l + r) / 2;
if(rnk(m) <= x) l = m;
else r = m;
// 我们称要找的数为 y
// 我们要寻找满足 rnk(y) 不大于 x,并使 y 最大
// 这个 y 最终会落在 左指针上
}
return l;
}
对于前驱后继,拥有了前两个操作的我们自然能较为轻松的解决。
代码如下↓
// 查询前驱
lst = at(rnk(x) - 1);
// 查询后继
lst = at(rnk(x + 1));
这里两个操作略微不同,对于第一个,由于
根号重构
虽然现在代码已经能够解决问题了,但我们还需要为其加上灵魂:根号重构。
当发现小数组的长度大于一定值时。我们新建一个 vector,用来存储更新后的大数组,我们只需要像归并排序一样将数组合并就行了,同时每往新数组里添加一个数,我们就检查第二个小数组里有没有值与其相同,如果有,那就意味着我们应该将其删除。最后,将新数组复制到大数组中,重构就完成了。
在此处的具体实现中往每个数组顶都加上了无限大的值,这是为了防止访问到非法内存然后狠狠吃 RE。
代码如下↓
if(max(l2.size(), l3.size()) >= BLK){
vector<ll> l4;
// 新数组
ll j = 0, k = 0;
l1.push_back(INF);
l2.push_back(INF + 5);
l3.push_back(INF + 5);
// 向数组顶填入 INF,防止 j k 哨兵节点越界
for(auto x : l1){
while(l2[j] <= x){
l4.push_back(l2[j]);
// l1 l2 交叉填入保证新数组有序
if(l4[l4.size() - 1] == l3[k]){
l4.pop_back();
k++;
}// 每次填入时检查其是否应该被删除
j++;
}
l4.push_back(x);
if(l4[l4.size() - 1] == l3[k]){
l4.pop_back();
k++;
}// 同上
}
l1.swap(l4);
l2.clear();
l3.clear();
// 清空 l2 l3
// 根号重构
}
其他优化
为了使该算法性能更好,我们可以尝试一些优化:
l1.reserve(n + 5);
l2.reserve(BLK + 5);
l3.reserve(BLK + 5);
我们为 vector 预先分配一些内存,这可以避免重复扩容产生额外开销。
vector 的 clear() 是有问题的,因为在清空后数组不会尝试释放空间,但这也意味着我们不必多次为两个小数组预留空间。
欣赏完整代码
::::info[代码如下↓]
#include<bits/stdc++.h>
#define fff(i , x , y) for(ll i = x; i <= y; ++i)
#define dff(i , x , y) for(ll i = x; i >= y; --i)
#define fin(a) freopen(a ,"r", stdin);
#define fot(a) freopen(a ,"w", stdout);
typedef long long ll;
using namespace std;
namespace fastio{
int innum(char c) {return ('0'<= c && c <='9');}
ll read(){
ll res = 0, f = 1, c = getchar();
for(; !innum(c); c = getchar()) if(c =='-') f = -1;
for(; innum(c); c = getchar()) res = res * 10 + (c ^ 48);
return res * f;
}
}// 读入优化
using namespace fastio;
const ll BLK = 2400, INF = 0x3f3f3f3f3f3f;
ll n, m, lst, res;
vector<ll> l1, l2, l3;
// l1 (大数组)存储集合中的数
// l2 (第一个小数组)数组暂时存储要加入的数
// l3 (第二个小数组)数组暂时存储要删除的数
ll rnk(ll x){
ll res = 0;
res += lower_bound(l1.begin(), l1.end(), x) - l1.begin();
res += lower_bound(l2.begin(), l2.end(), x) - l2.begin();
// l1 l2 表示加入的数
// 找到其中小于 x 的数的个数并相加
res -= lower_bound(l3.begin(), l3.end(), x) - l3.begin();
// l3 表示要删除的数
// 这些数在 l1 或 l2 中存在,但我们应该删除它
// 所以减去这些数对答案的贡献
return res + 1;
// 题目定义比 x 小的数 +1 即为排名
}
ll at(ll x){
ll l = -INF, r = INF;
while(l + 1 < r){
ll m = (l + r) / 2;
if(rnk(m) <= x) l = m;
else r = m;
// 我们称要找的数为 y
// 我们要寻找满足 rnk(y) 不大于 x,并使 y 最大
// 这个 y 最终会落在左指针上
}
return l;
}
int main(){
n = read();
m = read();
l1.reserve(n + 5);
fff(i, 1, n){
ll x = read();
l1.push_back(x);
}
sort(l1.begin(), l1.end());
// 读入并排序以维护有序性
l2.reserve(BLK + 5);
l3.reserve(BLK + 5);
fff(_, 1, m){
ll op = read(), x = read() ^ lst; // 异或解密
if(op == 1){ // 插入元素
l2.insert(lower_bound(l2.begin(), l2.end(), x), x);
} else if(op == 2){ // 删除元素
l3.insert(lower_bound(l3.begin(), l3.end(), x), x);
// 两个代码意思相近,都是往数组中加入 x 并维护有序性
// lower_bound 查找插入位置,insert 插入 x
// 因为数组原本有序,可以看成是插入排序的单次操作
} else if(op == 3){ // 查询一个数的排名
lst = rnk(x);
} else if(op == 4){ // 查询排名对应的数
lst = at(x);
} else if(op == 5){ // 查询前驱
lst = at(rnk(x) - 1);
} else { // 查询后继
lst = at(rnk(x + 1));
}
if(3 <= op && op <= 6){
res ^= lst;
} // 计入答案
if(max(l2.size(), l3.size()) >= BLK){
vector<ll> l4;
// 新数组
ll j = 0, k = 0;
l1.push_back(INF);
l2.push_back(INF + 5);
l3.push_back(INF + 5);
// 向数组顶填入 INF,防止 j k 哨兵节点越界
for(auto x : l1){
while(l2[j] <= x){
l4.push_back(l2[j]);
// l1 l2 交叉填入保证新数组有序
if(l4[l4.size() - 1] == l3[k]){
l4.pop_back();
k++;
}// 每次填入时检查其是否应该被删除
j++;
}
l4.push_back(x);
if(l4[l4.size() - 1] == l3[k]){
l4.pop_back();
k++;
}// 同上
}
l1.swap(l4);
l2.clear();
l3.clear();
// 清空 l2 l3
// 根号重构
}
}
cout << res <<'\n';
return 0;
}
/*
https://www.luogu.com.cn/record/310431081
*/
::::
复杂度分析
设
对于操作 1 2,每次操作的时间复杂度随数组大小线性相关,因为两个小数组大小与
对于操作 3,我们二分查找了 3 个数组,其中最大的数组大小与
对于操作 4,我们套了两层二分,一层与
对于操作 5 6,因为直接调用了操作 4,所以时间复杂度与操作 4 相同,也就是是
对于根号重构,每次操作只需要遍历一遍所有数组,故单次时间复杂度为
将所有操作复杂度相加,即可得到时间复杂度为
对于空间复杂度,由于我们只维护了若干个数组,所以空间复杂度很显然是
不难注意到当
虽然是根号算法,但是得益于算法的低常数,这个算法并不算慢,甚至在弱化版中,比我朋友打的平衡树还略快一些。
我的
朋友的
最后一些想说的
这个算法相比于平衡树等算法,很明显代码量很少,除了 STL,你只需要会二分和归并排序就行了。
当你想实现一些其他功能时,你也可以尝试进行一些拓展,例如给大数组挂一个树状数组,但像可持久化,区间翻转,合并分裂这些功能就不在我和这个数据结构的能力范围之内了。若你有什么建议,欢迎指点。