一种基于根号重构实现类似平衡树的功能的方法

· · 算法·理论

声明:该设想可能已经被其他人提出过,若有类似文章,麻烦联系我。

首先看一下这道题:一道平衡树的板子题。
可以看到,因为数据存在加强,所以无法通过离散化来规避,必须动态维护所有数字,而 std::set 等数据结构虽然能够直接使用,但显然无法维护题目所给的排名、前驱和后继等乱七八糟的信息,直接维护有序数组的话(a.k.a. 排序向量树),插入删除又是个灾难。所以我们必须手写平衡树或者跳表……吗?当然不是!

根号重构

根号重构可以用较为简单的方法维护集合。

很显然,我们在维护有序数组时,可以不用每次都将 x 插入到序列中,而是尝试将部分操作存在一个小数组中并排序,当积累的操作足够多时,将这个小数组与大数组合并。设小数组阈值为 T,则平均每操作 1 次花费 O(T) 的时间复杂度用于维护小数组的有序性,每操作 T 次花费 O(n) 的时间复杂度用于合并重构,当 T 取 \sqrt n 时,时间复杂度为 O(n \sqrt n),得益于数组操作的低常数,这已经足够我们完成题目了。

那我们具体该怎么做呢

预处理

我们先定义以下常量。

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)

查询

看起来需要我们实现的操作非常多,但其实我们只需要实现“查询一个数的排名”的功能,就可以基于此实现一些平衡树支持的其他功能,所以让我们一个一个来。

因为查询 x 的排名就相当于查询比 x 小的数的个数 +1,我们可以对三个数组分别使用 lower_bound 求出第一个大于等于 x 的数的位置,便可以得到小于 x 的数的个数(注意,因为第二个小数组表示要删去的数,所以我们应该减而不是加)。

代码如下↓

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 即为排名
}

对于查询排名为 x 的数,我们可以尝试二分,找到最大的排名小于等于 x 的数即为所求。

代码如下↓

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));

这里两个操作略微不同,对于第一个,由于 x 的排名指向第一个大于等于 x 的数,我们将函数值 -1 便能得到前驱的位置。而对于第二个,x + 1 的排名相当于大于 x 的数 +1,可以看的出,最小的大于 x 的数的排名与所求相等,所以将 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

*/

::::

复杂度分析

设 T 为重构阈值,n 为操作次数,V 为值域,则时间复杂度为 O(nT+\frac{n^2}{T} + n\log n \log V),下面贴出证明。

对于操作 1 2,每次操作的时间复杂度随数组大小线性相关,因为两个小数组大小与 O(T) 同阶,所以时间复杂度即为操作次数乘以数组大小,即为 O(nT)。

对于操作 3,我们二分查找了 3 个数组,其中最大的数组大小与 O(n) 同阶,所以时间复杂度即为数组大小的对数乘以操作次数,也就是 O(n \log n)。

对于操作 4,我们套了两层二分,一层与 V 有关,一层与 n 有关,时间复杂度即为 O(n\log n \log V)。

对于操作 5 6,因为直接调用了操作 4,所以时间复杂度与操作 4 相同,也就是是 O(n\log n \log V)。

对于根号重构,每次操作只需要遍历一遍所有数组,故单次时间复杂度为 O(n),因为我们至少每 T 次操作重构一次,故重构次数约为 \frac{n}{T},相乘即可得到复杂度为 O(\frac{n^2}{T})。

将所有操作复杂度相加,即可得到时间复杂度为 O(nT+\frac{n^2}{T} + n\log n \log V)。

对于空间复杂度,由于我们只维护了若干个数组,所以空间复杂度很显然是 O(n)。

不难注意到当 T=O(\sqrt{n}) 时时间复杂度最优,显然一般情况下 \log V \le 64 \ll \frac{\sqrt{n}}{\log n},因此最终复杂度可看作为 O(n \sqrt n),实际使用中 T 的取值应当根据常数自行上下调整。

虽然是根号算法,但是得益于算法的低常数,这个算法并不算慢,甚至在弱化版中,比我朋友打的平衡树还略快一些。

我的
朋友的

最后一些想说的

这个算法相比于平衡树等算法,很明显代码量很少,除了 STL,你只需要会二分和归并排序就行了。

当你想实现一些其他功能时,你也可以尝试进行一些拓展,例如给大数组挂一个树状数组,但像可持久化,区间翻转,合并分裂这些功能就不在我和这个数据结构的能力范围之内了。若你有什么建议,欢迎指点。