分享丨更快的sortedlistPlus

2219

2025.01.11

2025.08.11

发布于浙江

1.背景

最近看了下草莓奶昔《SortedList 源码浅析 (python)》
发现严格上来说sortedList的插入删除复杂度是 $O (n^{1/3})$ 的，而不像网上一些资料说得那样是 $O (l o g (n))$ 。
感觉不是非常完美，于是在其基础上加了一些优化，使其变成 $O (n^{1/5})$ ，不知道有没有人已经发明过了，姑且叫做sortedlistPlus吧。

2.使用场景

假设我们有一个容器，它需要支持以下四种操作：

往容器里添加一个给定元素x；
在容器里删除一个指定元素x；
查询一个元素x在容器里的名次rank；
查询容器里第rank个大的元素；

比较常见的做法有：

离散化之后线段树上二分，离散化之后树状数组上二分等。

缺点：必须事先知道所有可能的元素值进行离散化，因此不支持在线场景。

动态开点的线段树，动态开点的01字典树等。

缺点：单次操作时间复杂度是 $O (l o g (U))$ 的,(U是值域)，只支持整数类型,单次插入空间复杂度是 $O (1 + l o g (U / n))$ 。这类方法在时间和空间上开销都比较大。

平衡树(如红黑树，Treap，splay等)。

单次操作时间复杂度O(log(n)),单次插入空间复杂度O(1)。
这也比较推荐的方法，缺点相对较少。然而，相比第四种方法，平衡树的节点在内存中的分布不连续，常数开销较大。

分块及基于分块的其他方法，如sortedList，sortedlistPlus。

虽然单次插入删除的时间复杂度不是O(log(n))，但由于内存的连续，常数会非常小。在数据量不大的情况下元素数目在 $1 0^{5}$ 左右时，仅朴素分块 $O (n^{1/2})$ 就不输于 $O (l o g (n))$ 的平衡树。
下面主要介绍第四种。

3.分块类方法分析

3.1 单个数组-不分块 $O (n)$

使用单个数组维护一个有序列表，可以通过二分查找在O(log(n))时间找到给定元素的位置。
然而，在删除该元素或在其后插入新元素时，时间复杂度为O(n)，因为需要移动后续元素来保持数组连续，不能从中间断开。

3.2 朴素分块 $O (n^{1/2})$

假设我们有一个包含 12 个元素的有序列表:

[4,8,9,10,13,17,21,25,30,33,37,41]

可以将这个列表分成 3个大小为 4的块，每个块存储 4个元素：

块 1: [4, 8, 9, 10]
块 2: [13, 17, 21, 25]
块 3: [30, 33, 37, 41]

相邻的两个元素要么在同一个块内，要么一个在块尾，另一个在下一个块的块首。例如，元素 10和 13 分别位于块1和块 2 的末尾和开头。

3.2.1 朴素分块插入和删除元素

为了防止所有元素都插入到同一个块，从而退化到3.1单个数组，需要设定一个负载因子load,块内元素个数达到2load时，把一个块分裂成两个相邻的块。

首先查找指定元素x位置：

现在块与块之间二分，查找到哪个块的最后一个元素大于等于x；
然后在块内部二分。
复杂度为： O(log(n/load))+O(log(load))=O(log(n))。

插入/删除元素的复杂度为： $O (l o a d + n / l o a d^{2})$ 。
这里解释一下 $n * l o a d^{- 2}$ 项，块大小是load，那么块的个数就是 $n * l o a d^{- 1}$ 。

每当一个块内元素个数从load增加到 $2 l o a d$ 个时会进行一次分裂，后面的块会右移一个位置。
平均load次增加元素会使块进行一次 $n * l o a d^{- 1}$ (块的个数)的平移，均摊复杂度 $n * l o a d^{- 2}$ 。
删除块同理，平均删除load个元素会使一个中间的块内元素个数从load减少到0，后面所有块左移一个位置。

3.2.2 朴素分块查找指定元素x的rank

初始rank:=0
按块的顺序遍历，如果当前块最大值(块的最后一个元素)小于x, rank+=当前块的大小，然后进入下一个块。
如果当前块最大值(块的最后一个元素)大于等于x，在块内部二分, rank += lower_bound(x), 停止遍历块。
复杂度是：O(n/load+log(load))。

3.2.3 朴素分块查找第rank大元素

按块的顺序遍历，如果当前块大小<=rank, rank-=当前块的大小，然后进入下一个块。
如果当前块大小>rank，return blocks[bi][rank]。这一步是O(1)的。
这里bi表示块的下标，rank表示块内元素的下标。
复杂度是：O(n/load)。

3.2.4 平均复杂度

假设 插入和删除元素 和 查找第rank大元素操作数目在同一量级,
那么平均单次操作复杂度：
$O (l o a d + n / l o a d^{2} + n / l o a d) >= O (n^{1/2})$ ；
当 $l o a d = n^{1/2} 时不等式取等$ 。
分块思想-wiki

3.3 sortedlist $O (n^{1/3} + O (l o g (n)))$

3.3.1 sortedlist插入和删除元素

插入/删除元素操作和朴素分块相同。复杂度为： $O (l o a d + n / l o a d^{2})$ 。

3.3.2 sortedlist查找指定元素x的rank

这里跟朴素分块有区别了：
建立一个线段树，树的叶节点表示一个块的元素个数，线段树的区间合并操作为数值相加。
这样线段树的非叶节点，就代表了一段区间内，对应的所有块的元素个数之和。

在O(log(n/load))的时间内二分查找到x位于哪个块，记块下标为bi。
用线段树query(0,bi-1)计算当前块左边的块的元素和s。
在块内二分找到x在块内的下标bj。x在整个有序列表的rank=s+bj。
复杂度：O(log(n/load))+O(log(load))=O(log(n)) 。

3.3.3 sortedlist查找第rank大元素

在线段树上二分，当前树节点记为u。

如果左子树代表的区间的块的元素个数和大于rank,则进入左子树查找。
否则rank-=sum[left[u]], 然后进入右子树查找更新后的rank。
树上二分找到块下标bi后，blocks[bi][rank]就是要找的元素(此时rank经过更新，已经减去bi左边的块的元素个数和)。
复杂度：O(log(n/load))。树的大小跟块的个数(n/load)是同一量级，第3步是O(1)。

3.3.4 线段树重构

回到3.3.1插入和删除元素。

插入元素时，平均插入load个元素会使一个块分裂。
删除元素时，平均删除load个元素删除一个块。

线段树的叶节点是同某个块的元素个数一一对应的。某块分裂或删除后，后续的块的下标全部发生变化，不再和线段树对应。
此时需要重构线段树。重构一次线段树复杂度是 $O (n / l o a d)$ 。
平均load个插入或删除操作会引起一次线段树重构，因此均摊复杂度是 $O (n / l o a d^{2})$ 。

3.3.5 平均复杂度

假设四种操作复杂度在同一数量级，那么单次操作平均复杂度为 $O (l o a d + n / l o a d^{2} + O (l o g (n))) >= O (n^{1/3} + O (l o g (n)))$ ；
当 $l o a d = n^{1/3}$ 时取等。

4.sortedlistPlus $O (n^{1/5} + l o g (n))$

基本思路跟sortedlist类似。
首先python原生的sortedlist维护连续的块的元素个数和是用线段树实现的，常数较大，这部分可以用树状数组实现。
但这不是主要的，虽然树状数组常数更小，但理论本质上没有变化(复杂度不变)。

4.1 优化方向

注意到每次有一个数据块，块内元素个数达到2load或0时,块会进行分裂或删除。

此时后面的所有块就会进行移动，这一步开销O(n/load)。
然后维护块内元素个数的线段树(树状数组)会进行重构，这一步开销也是O(n/load)。
以上两个操作的均摊复杂度是 $O (\frac{n}{l o a d * l o a d})$

直观觉得这开销太大了，一言不合就重构线段树(树状数组)。

接下来不提线段树，维护块元素个数的任务由树状数组实现。

于是对维护块元素和的树状数组进行分段，相应的，每个树状数组节点对应一个小块，把小块也进行对应分段。
把原来的load改为load1,小块内元素个数达到2load1个时进行分裂，分裂成两个相邻的大小为load1的小块。
引入一个新的负载因子load2, 表示一个树状数组小段，对应load2个小块，大约对应 load1*load2 个元素，这样的树状数组小段有 $\frac{n}{l o a d 1 * l o a d 2}$ 个。
同样的，一个小段内的小块数目达到2load2时，把一个小段分裂成两个小段（这里不准确，但可以先这么理解。实际的操作是对所有非空块重新分配位置，load2个非空块之后放置load2个空块）。

如图：当前2load2=8,说明一个小段可以容纳的小块个数是1~7。
小段内非空小块数目达到8时，小段会分裂成两个小段，达到0时，小段会删除。
当前有5个小段，segSize表示小段内非空节点数目。当前segSize = [5,3,4,6,6]。

4.2 sortedlistPlus插入和删除元素

4.2.1 块内元素平移

在一个小块内插入或删除元素后，小块内部插入位置右边所有元素需要平移。
复杂度是O(load1)

4.2.2 段内重构

比如设置的load1=6,2load1=12。
小块内部元素个数到达12时将进行分裂，分裂成两个大小为6的块。
现在往28号小块内插入6个元素，小块内元素数目来到12，小块进行分裂，此时只需要对第4个小段进行重构。

注意小段重构时，第4段根节点32号，获得第25~32号小块元素数目和，数目和仅为34，此时还需要加上第3段根节点24号的贡献12，第二段根节点16号的贡献31。

因为16 + (-16 & 16) = 32; 24 + (-24 & 24) = 32;

一次段内重构的复杂度是：O(load2)。
小块分裂后，右边小块整体右移动一格，复杂度也是O(load2)。 (只有分裂小块右边到小段内部最后一个非空小块需要移动)。
一直往同一小块内增加元素，平均增加load1个元素，会进行一次小块分裂，此时需要进行一次小段内部重构。
因此均摊复杂度为： $O (\frac{l o a d 2}{l o a d 1})$ 。

4.2.3 整个树状数组重构

某一小段内小块数目到达2load2时，对整个树状数组进行重构。此时收集所有非空小块，对它们进行重新分配。
每放置load2个非空小块，就在后面放置load2个空块，方便小块分裂时仅需在小段内部寻找空块。
一共有n/load1个小块，重构复杂度为 $O (\frac{n}{l o a d 1})$ ;
平均load1次插入元素会使一个小块分裂，分裂load2个小块才会将一个小段充满。
因此均摊复杂度为： $O (\frac{n}{l o a d 1 * l o a d 1 * l o a d 2})$ ;

4.2.4 查找插入或删除的元素x的位置

此时需要根据x的值来寻找在哪一个小块，和块内的哪一个下标。
但是此时整个blocks有大约一半的小块是空的(为小块分裂预留位置)，于是不能直接在小块与小块之间直接二分。
有两种方法解决这个问题：
方法一：

先在小段与小段之间二分，因为小段一定是非空的，小段内非空小块个数为0时，就进行整个树状数组重构了。
二分比较x与某一小段的最后一小块的最后一个元素的大小，获取小段的索引。
小段个数为n/(laod1*load2),因此小段间二分复杂度为log( n/(laod1*load2) )。
在小段内部，非空小块之间二分。
小段内小块间二分复杂度为log(load2)。
在小块内二分，复杂度为log(load1)。
总复杂度：log(n/(laod1*load2)) + log(load2) + log(load1) = log(n)。

方法二：
建立小块最大元素的对应的树状数组blockMax。

在树状数组blockMax上二分。复杂度为O(n/load1)。
在小块内二分，复杂度为log(load1)。
总复杂度：log(n/load1 + log(load1) = log(n)。

4.3 sortedlistPlus查找指定元素x的rank

先利用4.2.4的操作寻找到x位于哪一个小块bi,和小块内部的下标bj。复杂度Olog(n)。
在树状数组上查询sum(blocks[1~bi-1])，即树状数组上bi-1节点的前缀和。复杂度Olog(n/load1)。
总复杂度 $Ol o g (n)$

4.4 sortedlistPlus查找第rank大元素

在树状数组上二分，寻找块号的同时减去前缀块的元素数目和。这一步的时间复杂度是O(log(n/load1))。
返回blocks[bi+1][k]。bi是最后一个前缀和<=初始rank的节点，k是初始rank减去sum(blockSize[1~bi])的贡献后剩余名次。
总复杂度O(log(n/load1))+O(1) = O(log(n/load1))。

4.5 平均复杂度

假设四种操作复杂度在同一数量级，那么单次操作平均复杂度为：
$O (l o a d 1) + O (\frac{l o a d 2}{l o a d 1}) + O (\frac{n}{l o a d 1 * l o a d 1 * l o a d 2}) + O (l o g (n))) >= O (n^{1/5} + O (l o g (n)))$ 。
当 $l o a d 1 = n^{1/5}$ , $l o a d 2 = n^{2/5}$ 时取等。

5. 分块类算法与平衡树比较：

对应单次操作的平均复杂度：

朴素分块： $O (n^{1/2} + l o g (n))$ ；
sortedlist： $O (n^{1/3} + l o g (n))$ ；
sortedlistPlus： $O (n^{1/5} + l o g (n))$ ；
平衡树： $O (l o g (n))$ 。

这四种算法都含有log(n)项，但分块类算法的log(n)都是在数组上二分，常数比平衡树小很多。
sortedlistPlus $n^{1/5}$ 增长非常慢，在5.7e6之前都是小于 $l o g_{2} (n)$ 的。
且大部分都是连续内存上的memmove等操作，常数比平衡树小得多,其他操作也都是对数组的遍历，常数也不大。
按我个人的估计，可能不太准：
n<1e5,朴素分块优于平衡树；n>1e5,平衡树优于朴素分块
n<1e6,sortedlist优于平衡树； n>1e6,平衡树优于sortedlist
n<1e9,sortedlistPlus优于平衡树；n>1e9,平衡树优于sortedlistPlus

6. 代码实现

用cpp分别对4.2.4提到的两种方法进行了实现。
以下是使用例子，注意到这道题目是sortedSet,所以要在insert的地方判断一下，无重复才insert。按list使用则不需要修改。
方法1：https://judge.yosupo.jp/submission/261128
方法2：https://judge.yosupo.jp/submission/261129

C++

template <typename _Tp = int, unsigned load1 = 200, unsigned load2 = 64>
struct sortedlistPlus {
    using Iterator = vector<_Tp>::iterator;
    const unsigned load1X = load1 * 2;
    const unsigned load2X = load2 * 2, lg2 = __lg(load2X);
    const _Tp minVal = std::numeric_limits<_Tp>::min();
    vector<vector<_Tp>> blocks; // blocks,bitCnt长度相同，都是1+小块的个数，≈n/load1
    vector<int> bitCnt;         // blocks每个元素中存的是一小块数据，bitCnt是小块.size()的树状数组
    vector<_Tp> blkMax;         // blkMax[i]中存blocks[i].back()
    vector<_Tp> segMax;         // segMax,segSize长度相同,都是小段的个数 ≈ n/(load1*load2), segMax表示小段内元素最大值
    vector<int> segSize;        // segSize表示小段内非空小块个数,segSize[i]∈[1,2load2-1]
    int elementCnt;
    sortedlistPlus() { clear(); }
    sortedlistPlus(vector<_Tp> A) {
        ranges::sort(A);
        elementCnt = A.size();
        blocks.reserve(elementCnt / load1 + 2);
        blocks.resize(1);
        for (int l = 0; l < elementCnt; l += load1)
            blocks.emplace_back(A.data() + l, A.data() + min<int>(l + load1, elementCnt));
        _expand();
    }
    void clear() {
        blocks.resize(1); // 0th位置空着,从1st小块开始存数，方便树状数组管理
        bitCnt.resize(1);
        blkMax.resize(1);
        segMax.clear(), segSize.clear();
        elementCnt = 0;
    }
    void chmax(_Tp &a, auto &&b) {
        if (b > a) a = b;
    }
    pair<int, Iterator> lower_bound(_Tp x) {              // 找到x的lower_bound在哪一个小块、块内的位置
        if (segSize.empty()) return {0, blocks[0].end()}; // SL为空
        int l = -1, r = segSize.size() - 1, mid;
        // 1.在小段和小段之间二分，一共n/(load1*load2)个小段，复杂度log(n)-log(load1)-log(load2)
        while (r - l > 1) if (segMax[mid = l + r >> 1] >= x) r = mid; else l = mid;
        // 最终的r就是小段编号segi;

        // 2.在小段内非空小块之间二分，小段内约load2个小块，复杂度log(load2)
        l = r << lg2 | 0;          // 即l = segi * load2X + 1, 小段首的小块;r<<lg2=segi
        r = r << lg2 | segSize[r]; // r表示小段内非空小块的右端点
        while (r - l > 1) if (blkMax[mid = l + r >> 1] >= x) r = mid; else l = mid;
        // 最终的r就是小块编号bi;

        /* 3.在小块内部二分，小块内部约load1个小段，复杂度log(load1),
            总复杂度log(n)-log(load1)-log(load2) + log(load2)  + log(load1) = log(n)*/
        return pair{r, (Iterator)ranges::lower_bound(blocks[r], x)};
    }
    pair<int, Iterator> upper_bound(_Tp x) { // 与lower_bound类似
        if (segSize.empty()) return {0, blocks[0].end()};
        int l = -1, r = segSize.size() - 1, mid;
        while (r - l > 1)
            if (segMax[mid = l + r >> 1] > x) r = mid;
            else l = mid;
        l = r << lg2 | 0;
        r = r << lg2 | segSize[r];
        while (r - l > 1)
            if (blkMax[mid = l + r >> 1] > x) r = mid;
            else l = mid;
        return pair{r, (Iterator)ranges::upper_bound(blocks[r], x)};
    }
    void _rangeBitModify(int b1, int b2) { // 一小段树状数组段内重构
        fill(bitCnt.data() + b1, bitCnt.data() + b2 + 1, 0);
        for (int i = b1; i <= b2; ++i) { // 复杂度O(b2-b1) = O(load2),注意不是O(load2·log(load2))
            if (blocks[i].size()) {
                bitCnt[i] += blocks[i].size(); // 利用blocks[b1~b2].size()重构bitCnt[b1~b2]
                blkMax[i] = blocks[i].back();
            }
            if (i + (-i & i) <= b2 and bitCnt[i])
                bitCnt[i + (-i & i)] += bitCnt[i];
        }
        //   ~(b2&load2X-1)表示b2是一个小段的根节点
        //  ~(b2&load2X*2-1)表示b2不止是一个小段的根节点, 而且它还需要吸收前面某些个小段的贡献
        //  比如b2 = 12*load2X, 那么b2还要加上10*load2X的贡献,因为12*load2X == 10*load2X+lowbit(10*load2X);
        //  如果b2 = 11*load2X, 那么b2小段前面没有任何小段对b2有贡献
        //  如果b2 = 12*load2X, lowb=4*load2X/2, 那么b2要加上(12-2)*load2X和(12-1)*load2X对应根节点的贡献
        for (int lowb = (-b2 & b2) / 2; lowb >= load2X; lowb >>= 1)
            bitCnt[b2] += bitCnt[b2 - lowb]; // 平均O(1),有一半的b2是没有前面小段对它产生贡献的，一半的一半有两个小段对b2段有贡献
    }
    void _expand() { // 整个SL重构
        vector<vector<_Tp>> blocksOld = move(blocks);
        int c = 0; // 非空小块数目
        for (auto &blk : blocksOld)
            c += blk.size() > 0;
        int segn = (c + load2 - 1) / load2; //  segn新的小段数目
        blocks.reserve(segn * load2X + 1);  //
        bitCnt.reserve(segn * load2X + 1);
        blkMax.reserve(segn * load2X + 1);
        int ec = elementCnt;
        clear(); elementCnt = ec; // SL所有数据全部清空, 保留elementCnt, expand不会改变elementCnt
        segMax.assign(segn, minVal);
        segSize.assign(segn, 0);
        for (int i = 0; auto &block : blocksOld) {      // O(n/load1)
            if (block.size()) {                         // 如果是非空小块
                segMax[i >> lg2 - 1] = block.back();    // 更新第i/load2段的最大值
                segSize[i >> lg2 - 1] += 1;             // 更新第i/load2段的小块数目
                blkMax.emplace_back(block.back());      // 把小块的元素最大值存到blkMax数组
                bitCnt.emplace_back(block.size());      // 把小块的元素数目写到树状数组
                blocks.emplace_back(move(block));       // 移动小块到新的blocks数组。 O(1)
                if ((++i & load2 - 1) == 0 and i < c) { // 新的一段前半段填满了，后半段补空段
                    /*  每填load2个小块就在后面填load2个空块,形成一个前半段放满，后半段为空的树状数组小段
                        小块分裂时可以占用空块, 只要重置对应小段的树状数组，不需要重置整个SL
                        只有当空位全部填满时才重构整个SL，均摊复杂度(load1*load2)^-1 * (n/load1) */
                    blocks.resize(blocks.size() + load2); // 往后填充load2个空块
                    bitCnt.resize(blocks.size());         // 往后填充load2个0
                    blkMax.resize(blocks.size());
                }
            }
        }
        // O(n/load1) 处理bitCnt树状数组前缀和
        for (int i = 1; i < bitCnt.size(); ++i)
            if (i + (-i & i) < bitCnt.size()) bitCnt[i + (-i & i)] += bitCnt[i];
    }
    void insert(_Tp x) {
        if (segSize.empty()) {
            ++elementCnt;
            blocks.emplace_back(vector<_Tp>{x});
            bitCnt.emplace_back(1);
            blkMax.emplace_back(x);
            segMax.emplace_back(x);
            segSize.emplace_back(1);
            return;
        }
        auto [bi, it] = lower_bound(x);
        // if(it != blocks[bi].end() and *it == x) return  ; // 已经存在
        ++elementCnt;
        for (int i = bi; i < bitCnt.size(); i += -i & i) // 在整个树状数组上更新 log(n/load1)
            bitCnt[i] += 1;
        blocks[bi].insert(it, x);
        int segi = (bi - 1) >> lg2; // 即(bi - 1) // load2X
        chmax(blkMax[bi], x);
        chmax(segMax[segi], x);                     // 更新 segMax[segi]
        if (blocks[bi].size() >= load1X) {          // blocks[bi]分裂
            int bj = (segi << lg2) | segSize[segi]; // bi所在的这一小段的最后一个非空小块;
            int bn = segi + 1 << lg2;               // bi所在的这一小段的最后一个小块(与bj区别在bn包括了空块, 表示树状数组小段的根节点)
            if (blocks.size() <= bn) {              // blocks[bn]还不存在，说明是最后一段，直接在blocks[bi+1]处insert
                blocks.insert(blocks.begin() + bi + 1, vector<_Tp>(blocks[bi].begin() + load1, blocks[bi].end()));
                bitCnt.resize(blocks.size()); // 在尾部加个元素，元素值先不管，因为下面这个小段的树状数组内容要重构
                blkMax.resize(blocks.size());
            } else {
                // 这里不能insert了，因为这不是最后一小段，后面可能还有好多小段，insert会把blocks[bn]推到下一个小段的首位;
                // 把blocks[bi+1~bj]移动到blocks[bi+2~bj+1]，(这个闭区间长度是bj-bi); O(load2)
                vector<_Tp>().swap(blocks[bj+1]);//释放blocks[bj+1]的资源，实际生产环境比较重要
                memmove(blocks.data() + bi + 2, blocks.data() + bi + 1, (bj - bi) * sizeof(vector<_Tp>));
                /*    此时blocks[bi+2]和blocks[bi+1]是同一个对象，把blocks[bi+1]内存清零(清的是&blocks[bi+1]处的内存，也就是
                   blocks.data()+bi+1处,不是blocks[bi+1].data()处的内存) , 防止因为blocks[bi+1]的操作释放blocks[bi+2]的资源*/
                memset(blocks.data() + bi + 1, 0, sizeof(vector<_Tp>));
                blocks[bi + 1] = vector<_Tp>(blocks[bi].begin() + load1, blocks[bi].end());
            }
            blocks[bi].resize(load1); // 把后半块数据给blocks[bi+1]后blocks[bi]缩到原来前半块
            if (++segSize[segi] == load2X) {
                _expand();                                                         // 这一小段树状数组填满了,把SL重构
            } else {                                                               // 重构一小段树状数组
                _rangeBitModify(segi << lg2 | 1, min<int>(bn, bitCnt.size() - 1)); // (segi<<lg2|1) == segi*load2X+1;表示这一小段树状数组的左端点
            }
        }
    }
    void erase(_Tp x) {
        if (segMax.empty() or segMax.back() < x) return; // 检查整个SL是否非空，检查SL内是否存在元素 >= x;
        auto [bi, it] = lower_bound(x);                  // segMax.back() >= x , 所以it不会指向end();
        if (*it > x) return;                             // 如果第一个>=x的元素不是x,说明SL内不存在x,直接返回。
        --elementCnt;
        for (int i = bi; i < bitCnt.size(); i += -i & i) // 在整个树状数组上更新 log(n/load1)
            bitCnt[i] -= 1;
        blocks[bi].erase(it);
        int segi = (bi - 1) >> lg2;
        int bj = (segi << lg2) | segSize[segi]; // bi所在的这一小段的最后一个非空小块;
        if (blocks[bi].empty()) {               // blocks[bi]空了,删除
            int bn = segi + 1 << lg2;           // bi所在的这一小段的最后一个小块(与bj区别在bn包括了空块, 表示树状数组小段的根节点)
            if (blocks.size() <= bn) {          // blocks[bn]还不存在，说明是最后一小段，直接erase(blocks[bi])
                blocks.erase(blocks.begin() + bi);
                blkMax.erase(blkMax.begin() + bi);
                bitCnt.resize(blocks.size());                            // bitCnt.size() 与 blocks.size()保持一致， 其实就是bitCnt.pop_back();
                if (--segSize[segi] == 0) {                              // 删除当前小块后，最后一小段也空了
                    segMax.pop_back(), segSize.pop_back();               // 小段数量减一
                } else {                                                 // 当前小段非空
                    _rangeBitModify(segi << lg2 | 1, bitCnt.size() - 1); // 仅把当前小段的树状数组重构
                    if (bi == bj) segMax[segi] = blocks[bj - 1].back();  // 万一删了最后一小块，会导致segMax[segi]变小，更新一下；
                }
            } else { // 不是最后一小段的情况
                // 把blocks[bi+1~bj]移动到blocks[bi~bj-1]，(这个闭区间长度是bj-bi); O(load2)
                if (--segSize[segi] == 0) { // 删除当前小块后，当前小段也空了
                    _expand();              // 把整个SL重构
                } else {                    // 当前小段非空，仅把当前小段的树状数组重构
                    vector<_Tp>().swap(blocks[bi]);//释放blocks[i]的资源，实际生产环境比较重要
                    memmove(blocks.data() + bi, blocks.data() + bi + 1, (bj - bi) * sizeof(vector<_Tp>));
                    // 此时blocks[bj]和blocks[bj-1]是同一个对象，把blocks[bj]内存清零,防止因为blocks[bj]的操作释放blocks[bj-1]的资源*/
                    memset(blocks.data() + bj, 0, sizeof(vector<_Tp>));
                    _rangeBitModify(segi << lg2 | 1, bn);               // 仅把当前小段的树状数组重构
                    if (bi == bj) segMax[segi] = blocks[bj - 1].back(); // 万一删了最后一小块，会导致segMax[segi]变小，更新一下；
                }
            }
        } else { // blocks[bi]非空, 不需要删除blocks[bi]小块, 小段内结构不变
            blkMax[bi] = blocks[bi].back();
            if (bi == bj) segMax[segi] = blocks[bi].back(); // 万一删了最后一小块的最后一个元素，会导致segMax[segi]变小，更新一下；
        }
    }
    int size() const { return elementCnt; }
    _Tp operator[](int k) { // SL中第k个大的元素，base:0
        assert(k >= 0 and k < elementCnt);
        int bi = 0;
        for (int i = 1 << __lg(bitCnt.size() - 1); i; i >>= 1)
            if ((bi | i) < bitCnt.size() and k - bitCnt[bi | i] >= 0) k -= bitCnt[bi |= i];
        // 如果k减去bitCnt[bi|i]的值后还是一个>=0的下标，那么bi|=i, k减去新的bitCnt[bi]
        //  更新完之后，sum(blocks[1~bi].size())已经被k减去了，k仍>=0; 且此时k-blocks[bi+1].size()将小于0;
        return blocks[bi + 1][k];
    }
    int rank(_Tp x) { //找到lower_bound(x)在整个数组中的下标
        if (segSize.empty()) return 0;
        auto [bi, it] = lower_bound(x);
        int rk = it - blocks[bi].begin(); // 在bi块内的rank + sum(blocks[1~bi-1].size());
        for (int i = bi - 1; i; i ^= -i & i)
            rk += bitCnt[i];
        return rk;
    }
    int count(_Tp x) {
        if (segSize.empty()) return 0;
        auto [bi, it] = upper_bound(x);
        int rk = it - blocks[bi].begin();
        for (int i = bi - 1; i; i ^= -i & i)
            rk += bitCnt[i];
        return rk - rank(x); // upper_bound - lower_bound
    }
    pair<int, Iterator> prev(pair<int, Iterator> iter) {
        auto &[bi, it] = iter;
        assert(bi > 1 or bi == 1 and it > blocks[bi].begin());                        // 检测bi>=1, 检测iter不指向SL的首元素
        if (it > blocks[bi].begin()) return {bi, std::prev(it)};                      // prev位于同一小块
        if ((bi & load2X - 1) != 1) return {bi - 1, std::prev(blocks[bi - 1].end())}; // prev位于同一小段的前一个小块

        // prev位于前一小段的最后一个非空小块 , 此时 (bi & load2-1) = 1
        int Segi = ((bi - 1) >> lg2);
        bi = (Segi - 1 << lg2) | segSize[Segi - 1]; // 前一小段的最后一个非空小块
        return {bi, std::prev(blocks[bi].end())};
    }
    _Tp lessEqual(_Tp x){ // 寻找最大的<=x的元素，即*prev(upper_bound)
        auto [bi,it] = upper_bound(x);
        if( not (bi > 1 or bi == 1 and it > blocks[bi].begin()) ) return _Tp(-1);
        return *prev(pair<int, Iterator>{bi,it}).second;
    }
    _Tp greaterEqual(_Tp x){ //寻找最小的>=x的元素，即*lower_bound
        auto [bi,it] = lower_bound(x);
        if(it == blocks[bi].end()) return _Tp(-1);
        return *it;
    }
}; sortedlistPlus<int> sl;

7.结尾

思路不复杂，但这代码给我写吐了，看看大伙能不能发现什么bug。