魔のkyo的BLOG

Heap（最大堆/最小堆）

发表于 2022-06-20 更新于 2024-06-09 分类于数据结构 Valine：本文字数： 5.3k 阅读时长 ≈ 5 分钟

C++ STL 有提供priority_queue，但是它没有接口修改已经加入队列的元素的优先级。有时候我们希望修改队列中元素的优先级，可以通过priority_queue + 最后更新的时间戳，例如用一个map或unordered_map存储每个key最后更新的时间戳，然后将重复的key和priority的pair加入到priority_queue中，在取得队头元素时根据时间戳判断是否丢弃，这可以解决大多数问题，但如果遇到插入和更新特别多的情况，为了避免priority_queue迅速膨胀，我们不得不自己实现最大堆。

实际上通过之前讲过的Treap稍加改造就可以得到一个可以动态更新key优先级的Heap

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

namespace detail {

template<typename KT, typename PT>
struct TreeNode {
    KT key;
    PT priority;
    int size;
    TreeNode* left;
    TreeNode* right;

    TreeNode(const KT& key, const PT& priority):key(key),priority(priority),size(1),left(NULL),right(NULL){}
};

template<typename KT, typename PT>
class TreeNodePool {
    int batchsize = 1024;
    vector<char*> memchunks;
    queue<char*> blocks;
public:
    ~TreeNodePool() {
        for(int i=0;i<memchunks.size();i++) {
            free(memchunks[i]);
        }
    }

    TreeNode<KT, PT>* create(const KT& key, const PT& priority) {
        if(blocks.empty()) {
            char* p = (char*)malloc(sizeof(TreeNode<KT, PT>)*batchsize);
            memchunks.emplace_back(p);
            for(int i=0;i<batchsize;i++) {
                blocks.push(p+sizeof(TreeNode<KT, PT>)*i);
            }
            batchsize *= 2;
        }
        char* p = blocks.front(); blocks.pop();
        return new (p)TreeNode<KT, PT>(key, priority);
    }

    void release(TreeNode<KT, PT>* p) {
        blocks.push((char*)p);
    }
};
} // namespace detail

template<typename KT, typename PT, typename CMPF=less<PT> >
class Heap {
public:
    // 插入或更新key对应的priority
    void upsert(const KT& key, const PT& priority) {
        erase(key);
        insert(key, priority);
    }
    // 查看堆顶key
    const KT& peek() const {
        return root->key;
    }
    KT& peek() {
        return root->key;
    }
    // 取出堆顶key
    KT pop() {
        KT result = peek();
        erase(result);
        return result;
    }

    bool empty() const {
        return size() == 0;
    }

    int size() const {
        return _size(root);
    }

private:
    int insert(const KT& key, const PT& priority) {
        return _insert(root, create_tree_node(key, priority));
    }

    void erase(const KT& key) {
        _erase(root, key);
    }

private:
    detail::TreeNode<KT, PT>* create_tree_node(const KT& key, const PT& priority) {
        return pool.create(key, priority);
    }
    
    void release_tree_node(detail::TreeNode<KT,PT>* root) {
        pool.release(root);
    }

    static int _size(detail::TreeNode<KT,PT>* root) {
        return (root != NULL ? root->size : 0);
    }

    // 返回root子树的size减去左右子树的size
    static int _count(detail::TreeNode<KT,PT>* root) {
        if(root == NULL) return 0;
        return _size(root) - _size(root->left) - _size(root->right);
    }

    static void lrotate(detail::TreeNode<KT,PT>* &root) {
        auto right = root->right;
        auto rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        int root_size = root->size;
        root->size += _size(rightleft) - _size(right);
        right->size = root_size;
        root = right;
    }

    static void rrotate(detail::TreeNode<KT,PT>* &root) {
        auto left = root->left;
        auto leftright = left->right;
        root->left = leftright;
        left->right = root;
        int root_size = root->size;
        root->size += _size(leftright) - _size(left);
        left->size = root_size;
        root = left;   
    }

    int _insert(detail::TreeNode<KT,PT>* &root, detail::TreeNode<KT,PT>* p) {
        if(root == NULL) {
            root = p;
            return 1;
        } else {
            if(p->key < root->key) {
                int r = _insert(root->left, p);
                root->size += r;
                if(CMPF()(root->priority, root->left->priority)){
                    rrotate(root);
                }
                return r;
            } else if(root->key < p->key) {
                int r = _insert(root->right, p);
                root->size += r;
                if(CMPF()(root->priority, root->right->priority)){
                    lrotate(root);
                }
                return r;
            } else {
                root->size += 1;
                release_tree_node(p);
                return 1;
            }
        }
    }

    static int _count(detail::TreeNode<KT,PT>* root, const KT& key) {
        if(root == NULL) return 0;
        if(key < root->key) return _count(root->left, key);
        else if(root->key < key) return _count(root->right, key);
        else return _count(root);
    }

    int _erase(detail::TreeNode<KT,PT>* &root, const KT& key) {
        if(root == NULL) return 0;
        if(key == root->key) {
            auto left = root->left;
            auto right = root->right;
            if(left == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = right;
                return root_count;
            } else if(right == NULL) {
                int root_count = _count(root);
                release_tree_node(root);
                root = left;
                return root_count;
            } else {
                int root_count = _count(root);
                int r = 0;
                if(CMPF()(left->priority, right->priority)) {
                    lrotate(root); // 把优先级大的孩子转成根
                    r = _erase(root->left, key);
                } else {
                    rrotate(root);
                    r = _erase(root->right, key);
                }
                root->size -= r;
                return r;
            }
        } else if(key < root->key) {
            int r = _erase(root->left, key);
            root->size -= r;
            return r;
        } else {
            int r = _erase(root->right, key);
            root->size -= r;
            return r;
        }
    }

private:
    detail::TreeNodePool<KT, PT> pool;
    detail::TreeNode<KT, PT>* root = NULL;
};

SegTree（线段树）

发表于 2022-06-20 更新于 2024-11-18 分类于数据结构 Valine：本文字数： 11k 阅读时长 ≈ 10 分钟

什么是线段树？

线段树是一棵二叉树，每个节点维护一个区间和区间上的值，是一种用来维护 区间信息 的数据结构。

我们先从线段树能提供的操作上来理解。想象一个数组，每个下标上可以存一个值。所谓区间就是一段连续的数组下标。

我们可以进行的操作有：

1）区间赋值：设置一个区间内所有下标对应的值

2）单点赋值：设置单点的值

3）区间查询：查询一个区间内的最大值 / 最小值 / 值的和

4）单点查询：查询一个点的值

如果用数组来实现上述操作，所有区间操作的时间复杂度都是O(n)，n是区间长度，单点操作的复杂度都是O(1)，而线段树可以把上述全部操作的时间复杂度同时变成O(logn)

线段树的实现

根据维护的信息和支持的操作不同线段树分很多种，常用的有：着色线段树、覆盖线段树、求和线段树、最值线段树。

计数线段树：可以对区间反复覆盖，动态查询单点的覆盖次数。

着色线段树：可以对区间反复着色，动态查询单点的颜色。

求和线段树：可以对单点或区间赋值，动态查询区间数据的和。

最值线段树：可以对单点或区间赋值，动态查询区间数据的最值。

为了方便起见我用求和线段树进行讲解，并且只实现两种操作：

1）对单点赋值。

2）查询区间和。

假设我们有一个数组

1	arr = {3, 8, 3, 3, 5, 6, 8, 7};

通常情况比如我们求区间[2,7)的和需要遍历区间上的元素，O(区间长度)，如何减少运算次数呢，最简单的思路是我们预处理前缀和sum[]，令

1	sum[i]= arr[0]+arr[1]+...+arr[i-1]

当我们需要算[2,7)的区间和，其实就算[0,7)前缀和减去[0,2)的前缀和，即sum[7]-sum[2]，这样就可以用O(1)的时间算出任意区间的和，如果数组元素不会发生动态变化这样是可以的，但如果需要交替修改数组元素和查询区间和，这样处理会导致前缀和维护的成本很高，原本的arr[i]=x，我们不得不修改所有k>i的sum[k]来维护前缀和，这样修改数组元素的时间就从原本的O(1)变成了O(n)。

有没有方法可以在修改单点值的便利性和查询区间和的便利性上做个折中呢，肯定是有的，我们可以预处理一些子段和而不是所有前缀和，让修改单点值和查询区间和都只需要访问O(logn)的元素，树状数组和线段树都是类似这个思想，其实树状数组的设计更符合这个思想，但它只能用于求和，树状数组能做的线段树都能做，我们之后有空再讲树状数组，对于线段树我们先在这个数组上生成一个子段和数组，让

1	b = { arr[0]+arr[1], arr[2]+arr[3], arr[4]+arr[5], arr[6]+arr[7]} = {11, 6, 11, 15};

这样求区间[2, 7)的和的时候，可以取b[1] + b[2] + arr[6]，只需要算三个数的和就行了。

更近一步，我们可以在数组b上再合并建立 c = { b[0]+ b[1], b[2]+b[3], …}, d, e, …，直至把整个数组合并成一个元素，如下图

这样之后，对于这个数组上的任意区间的和都可以只取O(logn)的元素的和来得到。

为了方便，我们通过二叉树来维护这些数据，我们把最上面的整个数组的和43作为二叉树的根，同时记住这个节点对应的左右端点即0和8，我们把这个节点的数据表示为（0, 8, 43），然后把它的左孩子就是如图的和为17的节点，数据为(0, 4, 17)，同理右孩子(4, 8, 26)，以此类推，这样就可以建立一颗完全二叉树（我这里有意将数组的大小选为2的幂，如果不是2的幂我们也可以扩充到2的幂来建树）。

对于修改单点值的操作，我们要从树根一直修改到叶子，正好修改了树的深度个节点，复杂度也是O(logn)。

因为是完全二叉树，我们可以通过数组来实现，用data[0]作为根，data[k]的孩子是data[2*k+1]和data[2*k+2]

#include <iostream>
using namespace std;

#define MAXN 8
int bg[MAXN*2]; // 区间左端点，闭
int nd[MAXN*2]; // 区间右端点，开
int sm[MAXN*2]; // 节点值，即区间和

// 递归构建树
void build(int k, int b, int e) {
    bg[k] = b;
    nd[k] = e;
    sm[k] = 0;
    if(e-b>1) {
        int mid = b + (e-b) / 2;
        build(k*2+1, b, mid);
        build(k*2+2, mid, e);
    }
}

// 设置数组下标i的元素值，类似arr[i] = val
void change(int k, int i, int val) {
    if(nd[k]-bg[k]==1) { // 叶子节点
        sm[k] = val; // 直接更新
    } else {
        int mid = bg[k] + (nd[k]-bg[k]) / 2;
        // 递归向下更新
        if(i<mid) change(k*2+1, i, val);
        else change(k*2+2, i, val);
        // 回溯时通过孩子的值更新当前节点值
        sm[k] = sm[k*2+1] + sm[k*2+2];
    }
}

// 查询[b, e)的元素和
int query(int k, int b, int e) {
    if(b<=bg[k] && nd[k]<=e) {
        cout << "DEBUG:[" << bg[k] << "," << nd[k] << ") sm[k]=" << sm[k] << endl;
        return sm[k];
    }
    int mid = bg[k] + (nd[k]-bg[k]) / 2;
    return (b<mid ?query(k*2+1, b, e):0) + (mid<e ? query(k*2+2, b, e):0);
}

// 把n向上对齐到2的幂
int align(int n) {
    if(n & (n-1)) {
        while(n & (n-1)) {
            n &= (n-1);
        }
        n = (n << 1);
    }
    return n;
}

int main()
{
    int arr[] = {3,8,3,3,5,6,8,7};
    build(0, 0, align(8));
    for(int i=0;i<8;i++) {
        change(0, i, arr[i]);
    }
    cout << query(0, 2, 7) << endl;
}

输出

DEBUG:[2,4) sm[k]=6
DEBUG:[4,6) sm[k]=11
DEBUG:[6,7) sm[k]=8
25

可以看到，和预期的一样，只通过3个节点的值求和算出了区间[2,7)的和为25。

最值线段树

对于最大值、最小值的线段树，我们只需要把更新节点值的代码改掉。

区间更新

对于区间更新，例如把[a,b)的值全部设置为x，或者让[a,b)的值全部增加x，我们不能对区间内的点逐一更新，否则复杂度会变成O(nlogn)了，区间更新时，我们要引入懒惰标志，我们还是从根开始拆分区间，如果当前节点的区间被完全覆盖，我们就更新当前节点值并不向下继续更新，并把待更新的值记在懒惰标志内，直到查询需要用到节点值时再逐级更新并把懒惰标志一层层推下去。

离散化

我们可以看到上述线段树实现方式使用的数据空间是数组最大下标的2倍，有时候区间的范围很大，但区间的更新和查询操作的数量并不多，我们可以先统计所有的区间端点，比如有n个端点，然后排序，在所有区间端点和 0,1,…,n-1 之间做一一映射，然后就可以把线段树的空间降到 2*n，和区间个数相关而和区间范围无关。

动态开点

我们也可以不用数组表示的完全二叉树来实现线段树，而用一棵记录左右孩子指针的动态申请空间的普通二叉树，根据更新的区间来动态生成区间节点，这一般被称作动态开点。

支持区间更新的最大值线段树的完整实现


const int INF = 1e9+7;

// 最大值线段树
class SegTree {
    vector<int> nums;
    vector<int> d;
    vector<int> b;  // lazy
    vector<bool> v; // true: b中是设置值 false: b中是增量值

    void build(int s, int t, int p = 1) {
        // 对 [s,t] 区间建立线段树,当前根的编号为 p
        if (s == t) {
            d[p] = nums[s];
            return;
        }
        int m = s + ((t - s) >> 1);
        // 移位运算符的优先级小于加减法，所以加上括号
        // 如果写成 (s + t) >> 1 可能会超出 int 范围
        build(s, m, p * 2);
        build(m + 1, t, p * 2 + 1);
        // 递归对左右区间建树
        d[p] = std::max(d[p * 2], d[(p * 2) + 1]);
    }

    // [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
    // 为当前节点的编号
    void add(int l, int r, int c, int s, int t, int p) {
        // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
        if (l <= s && t <= r) {
            if(v[p]) {
                pushdown(s, t, p);
            }
            d[p] += c;
            b[p] += c;
            v[p] = 0;
            return;
        }
        pushdown(s, t, p);
        int m = s + ((t - s) >> 1);
        if (l <= m) add(l, r, c, s, m, p * 2);
        if (r > m) add(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = std::max(d[p * 2], d[p * 2 + 1]);
    }

    // [l, r] 为修改区间, c 为被修改的元素的值, [s, t] 为当前节点包含的区间, p
    // 为当前节点的编号
    void set(int l, int r, int c, int s, int t, int p) {
        if (l <= s && t <= r) {
            d[p] = c;
            b[p] = c;
            v[p] = 1;
            return;
        }
        pushdown(s, t, p);
        int m = s + ((t - s) >> 1);
        if (l <= m) set(l, r, c, s, m, p * 2);
        if (r > m) set(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = std::max(d[p * 2], d[p * 2 + 1]);
    }

    void pushdown(int s, int t, int p) {
        if(v[p]) { // 如果是设置值
            d[p * 2] = b[p];
            d[p * 2 + 1] = b[p];
            // 设置值可以清掉增量值而不用管之前b中是否有待增量懒值
            b[p * 2] = b[p * 2 + 1] = b[p];
            v[p * 2] = v[p * 2 + 1] = 1;
            b[p] = 0;
            v[p] = 0;
        } else { // 如果是增量值
            if(b[p]) {
            	int m = s + ((t - s) >> 1);
                // 如果子节点有待设置的懒值
                if(v[p * 2]) {
                    pushdown(s, m, p * 2);
                }
                if(v[p * 2 + 1]) {
                    pushdown(m + 1, t, p * 2 + 1);
                }
                // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
                d[p * 2] += b[p];
                d[p * 2 + 1] += b[p];
                b[p * 2] += b[p];
                b[p * 2 + 1] += b[p];  // 将标记下传给子节点
                b[p] = 0;              // 清空当前节点的标记
            }
        }
    }

    int getmax(int l, int r, int s, int t, int p) {
        // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
        if (l <= s && t <= r) return d[p];
        // 当前区间为询问区间的子集时直接返回当前区间的和
        int m = s + ((t - s) >> 1);
        pushdown(s, t, p);
        int max_value = -INF;
        if (l <= m) max_value = std::max(max_value, getmax(l, r, s, m, p * 2));
        if (r > m) max_value = std::max(max_value, getmax(l, r, m + 1, t, p * 2 + 1));
        return max_value;
    }
public:
    SegTree(int size): nums(size) {
        d.resize(size*4);
        b.resize(size*4);
        v.resize(size*4);
        build(0, nums.size()-1, 1);
    }

    SegTree(const vector<int>& a): nums(a) {
        d.resize(a.size()*4);
        b.resize(a.size()*4);
        v.resize(a.size()*4);
        build(0, nums.size()-1, 1);
    }

    // 对区间[b, e)的值增加c
    void add(int b, int e, int c) {
        add(b, e-1, c, 0, nums.size()-1, 1);
    }

    // 将区间[b, e)的值设置为c
    void set(int b, int e, int c) {
        set(b, e-1, c, 0, nums.size()-1, 1);
    }

    // 得到区间[b, e)上的最大值
    int max(int b, int e) {
        if(e<=b) return -INF;
        return getmax(b, e-1, 0, nums.size()-1, 1);
    }

private:
    class ItemAccessor {
    public:
        ItemAccessor(SegTree& st, int i): st(st), i(i) {}
        ItemAccessor& operator = (int x) {st.set(i, i+1, x);return *this;}
        ItemAccessor& operator += (int x) {st.add(i, i+1, x);return *this;}
        ItemAccessor& operator -= (int x) {st.add(i, i+1, x);return *this;}
        operator int() const {return st.max(i, i+1);}
    private:
        SegTree& st;
        int i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(SegTree& st, int b, int e):st(st), b(b), e(e) {}
        void operator = (int x) {st.set(b, e, x);}
        void operator += (int x) {st.add(b, e, x);}
        void operator -= (int x) {st.add(b, e, x);}
    private:
        SegTree& st;
        int b;
        int e;
    };

public:
    // 通过下标访问单点值的语法糖
    ItemAccessor operator [] (int i) {
        return ItemAccessor(*this, i);
    }

    // 通过下标访问区间值的语法糖
    RangeAccessor operator [] (const tuple<int, int>& range) {
        return RangeAccessor(*this, std::get<0>(range), std::get<1>(range));
    }
};

支持区间更新的求和线段树的完整实现

const int INF = 1e9+7;

// 求和线段树
class SegTree {
    vector<int> nums;
    vector<int> d;
    vector<int> b;  // lazy
    vector<bool> v; // true: b中是设置值 false: b中是增量值

    void build(int s, int t, int p = 1) {
        // 对 [s,t] 区间建立线段树,当前根的编号为 p
        if (s == t) {
            d[p] = nums[s];
            return;
        }
        int m = s + ((t - s) >> 1);
        // 移位运算符的优先级小于加减法，所以加上括号
        // 如果写成 (s + t) >> 1 可能会超出 int 范围
        build(s, m, p * 2);
        build(m + 1, t, p * 2 + 1);
        // 递归对左右区间建树
        d[p] = d[p * 2] + d[(p * 2) + 1];
    }

    // [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
    // 为当前节点的编号
    void add(int l, int r, int c, int s, int t, int p) {
        // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
        if (l <= s && t <= r) {
            if(v[p]) {
                pushdown(s, t, p);
            }
            d[p] += c * (t - s + 1);
            b[p] += c;
            v[p] = 0;
            return;
        }
        pushdown(s, t, p);
        int m = s + ((t - s) >> 1);
        if (l <= m) add(l, r, c, s, m, p * 2);
        if (r > m) add(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }

    // [l, r] 为修改区间, c 为被修改的元素的值, [s, t] 为当前节点包含的区间, p
    // 为当前节点的编号
    void set(int l, int r, int c, int s, int t, int p) {
        if (l <= s && t <= r) {
            d[p] = c * (t - s + 1);
            b[p] = c;
            v[p] = 1;
            return;
        }
        pushdown(s, t, p);
        int m = s + ((t - s) >> 1);
        if (l <= m) set(l, r, c, s, m, p * 2);
        if (r > m) set(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }

    void pushdown(int s, int t, int p) {
    	int m = s + ((t - s) >> 1);
        if(v[p]) { // 如果是设置值
            d[p * 2] = b[p] * (m - s + 1);
            d[p * 2 + 1] = b[p] * (t - m);
            // 设置值可以清掉增量值而不用管之前b中是否有待增量懒值
            b[p * 2] = b[p * 2 + 1] = b[p];
            v[p * 2] = v[p * 2 + 1] = 1;
            b[p] = 0;
            v[p] = 0;
        } else { // 如果是增量值
            if(b[p]) {
                // 如果子节点有待设置的懒值
                if(v[p * 2]) {
                    pushdown(s, m, p * 2);
                }
                if(v[p * 2 + 1]) {
                    pushdown(m + 1, t, p * 2 + 1);
                }
                // 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
                d[p * 2] += b[p] * (m - s + 1);
                d[p * 2 + 1] += b[p] * (t - m);
                b[p * 2] += b[p];
                b[p * 2 + 1] += b[p];  // 将标记下传给子节点
                b[p] = 0;              // 清空当前节点的标记
            }
        }
    }

    int getsum(int l, int r, int s, int t, int p) {
        // [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
        if (l <= s && t <= r) return d[p];
        // 当前区间为询问区间的子集时直接返回当前区间的和
        int m = s + ((t - s) >> 1);
        pushdown(s, t, p);
        int sum = 0;
        if (l <= m) sum += getsum(l, r, s, m, p * 2);
        if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
        return sum;
    }
public:
    SegTree(int size): nums(size) {
        d.resize(size*4);
        b.resize(size*4);
        v.resize(size*4);
        build(0, nums.size()-1, 1);
    }

    SegTree(const vector<int>& a): nums(a) {
        d.resize(a.size()*4);
        b.resize(a.size()*4);
        v.resize(a.size()*4);
        build(0, nums.size()-1, 1);
    }

    // 对区间[b, e)的值增加c
    void add(int b, int e, int c) {
        add(b, e-1, c, 0, nums.size()-1, 1);
    }

    // 将区间[b, e)的值设置为c
    void set(int b, int e, int c) {
        set(b, e-1, c, 0, nums.size()-1, 1);
    }

    // 得到区间[b, e)上的值的和
    int sum(int b, int e) {
    	if(e<=b) return 0;
        return getsum(b, e-1, 0, nums.size()-1, 1);
    }

private:
    class ItemAccessor {
    public:
        ItemAccessor(SegTree& st, int i): st(st), i(i) {}
        ItemAccessor& operator = (int x) {st.set(i, i+1, x);return *this;}
        ItemAccessor& operator += (int x) {st.add(i, i+1, x);return *this;}
        ItemAccessor& operator -= (int x) {st.add(i, i+1, x);return *this;}
        operator int() const {return st.sum(i, i+1);}
    private:
        SegTree& st;
        int i;
    };

    class RangeAccessor {
    public:
        RangeAccessor(SegTree& st, int b, int e):st(st), b(b), e(e) {}
        void operator = (int x) {st.set(b, e, x);}
        void operator += (int x) {st.add(b, e, x);}
        void operator -= (int x) {st.add(b, e, x);}
    private:
        SegTree& st;
        int b;
        int e;
    };

public:
    // 通过下标访问单点值的语法糖
    ItemAccessor operator [] (int i) {
        return ItemAccessor(*this, i);
    }

    // 通过下标访问区间值的语法糖
    RangeAccessor operator [] (const tuple<int, int>& range) {
        return RangeAccessor(*this, std::get<0>(range), std::get<1>(range));
    }
};

Python容器初始化技巧

发表于 2022-06-14 更新于 2024-06-09 分类于开发 Valine：本文字数： 1.1k 阅读时长 ≈ 1 分钟

类比C++ STL容器，记录Python容器初始化的一些技巧和陷阱

初始化一个集合的数组

C++写法

1	vector<set<int>> a(n);

正确的Python写法

1	a = [set() for i in range(n)]

一个错误的Python写法

1	a = [set()] * n

如果是常数值，这样写没问题，但是set()是对象，这会导致a[0] a[1] … a[n-1] 存储的都是指向同一个set对象的引用

初始化一个整数到整数集合的映射

C++写法

map<int, set<int>> b;

for(int i=0;i<10;i++) {
    b[i].insert(i);  // 在首次访问b[i]时会自动创建一个空的set<int>，所以可以直接调用insert
}

有用的但不舒服Python写法

b = {}
for i in range(10):
	if i not in b:  # 首次使用b[i]前要先判断并初始化
        b[i] = set()
    b[i].add(i)

defaultdict

有用且舒服的Python写法

from collections import defaultdict

b = defaultdict(set)  # 这里指定了dict的值类型
for i in range(10):
    b[i].add(i)  # 这里就可以像C++一样直接add了

嵌套defaultdict

如果我们想定义一个二重嵌套的defaultdict，类似map<int, map<int>>，不能简单地使用 defaultdict(defaultdict(int))，因为defaultdict需要传递的参数是一个类型T，可以通过T()构造出默认的对象，而defaultdict(int)是对象而不是对象的类型，其实关键是通过T()能得到构造出默认对象就可以，所以我们可以定义一个方法返回defaultdict(int)

1
2
3

def defaultdict_int_creator():
	return defaultdict(int)
defaultdict(defaultdict_int_creator)

这样就可以定义一个二重嵌套的defaultdict，更简单地，我们可以把函数改成lambda表达式

# 二重嵌套 defaultdict
defaultdict(lambda: defaultdict(int))
# 三重嵌套 defaultdict
defaultdict(lambda: defaultdict(lambda: defaultdict(int)))

质数

发表于 2022-06-09 更新于 2024-06-09 分类于算法 Valine：本文字数： 3.9k 阅读时长 ≈ 4 分钟

质数（又称素数）：只能被1和自身整除的大于1的正整数。

质数是初等数论的重要研究对象，有关质数的常用算法有如下一些：

线性筛法：O(n)时间筛出n以内的所有质数

质数判定：判断给定数n是否是质数。大质数判定有Miller Rabin测试法

合数分解：找到给定合数n的一个非平凡因子。大数分解有Pollard Rho分解法

BTW：一些和整除、因子、质数相关的题目，先做质因数分解会后豁然开朗，int范围内的数至多有1300多个因子，先分解再枚举所有因子，甚至对所有因子双层循环的时间都是可以接受的。

下面给出一个包含线性筛、Miller Rabin测试、Pollard Rho分解、质因数分解的质数工具类

#include <iostream>
#include <cmath>
#include <cassert>
#include <map>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

template<typename T>
T gcd(T a, T b) { while(b) { T r = a%b; a = b; b = r;} return a;}
template<typename T>
T lcm(T a, T b) { return a/gcd(a,b)*b; }

// 打表大小，[0, UPBOUND)查表，[UPBOUND, UPBOUND*UPBOUND)根据表测试，[UPBOUND*UPBOUND, ll_max)米勒罗宾测试
const ll UPBOUND = 5e6;
class CPrime {
public:
    ll modMul(ll a,ll b,ll m) {
        ll t=0;
        a=(a%m+m)%m;
        b=(b%m+m)%m;
        while(b){
            if(b&1){
                t=(t+a)%m;
            }
            a=(a+a)%m;
            b>>=1;
        }
        return t;
    }

    ll modExp(ll a,ll b,ll m) {
        ll t=1,y=a%m;
        while(b){
            if(b&1){
                t=modMul(t,y,m);
            }
            y=modMul(y,y,m);
            b=(b>>1);
        }
        return t;
    }

    bool miller_rabin(ll n,ll b) {
        ll m=n-1;
        int j=0;
        while(!(m&1)){
            m>>=1;
            j++;
        }
        ll v=modExp(b,m,n);
        if(v==1 || v==n-1)return 1;
        for(int i=1;i<j;i++){
            v=modMul(v,v,n);
            if(v==n-1)return 1;
        }
        return 0;
    }

    bool _isprime(ll n)
    {
        const int K=10;//Miller_Rabin的偏真正确率为75%， isprime的正确率为1-(1/4)^K
        if(n<2)return 0;
        if(n==2 || n==3)return 1;
        for(int i=0;i<K;i++){
            if(!miller_rabin(n,rand()%(n-2)+2))return 0;
        }
        return 1;
    }

    //pollard_rho分解，给出N的一个非1因数，返回N时为一次没有找到,C为一个[1,N]的随机数 
    ll pollard_rho(ll C, ll N)
    {
        ll I, X, Y, K, D;
        I = 1;
        X = rand() % N;
        Y = X;
        K = 2;
        do{
            I++;
            D = gcd(N + Y - X, N);
            if (D > 1 && D < N) return D;
            if (I == K) Y = X, K *= 2;
            X = (modMul(X, X, N) + N - C) % N;
        }while (Y != X);
        return N;
    }

    //找出N的最小(质)因数
    ll _min_divisor(ll N)
    {
        if (isprime(N)) return N;
        while(1){
            ll T = pollard_rho(rand() % (N - 1) + 1, N);
            if (T < N){
                  ll A, B;
                  A = _min_divisor(T);
                  B = _min_divisor(N / T);
                  return A < B ? A : B;
            }
        }
    }

    int a[UPBOUND];
    int p[UPBOUND];
    int pn = 0;

    //号称线性的筛素数算法，实际性能确实不错 
    //p[]={2,3,5,7,...},pn为小于UPBOUND的素数个数 
    //若i是合数a[i]为i的最小因子，若i是素数a[i]=0 
    void primefilter(){
        int i, j;
        for(i = 2; i < UPBOUND; ++i){
            if(!(a[i])) p[pn++] = i;
            for(j = 0; (j<pn && i*p[j]<UPBOUND && (p[j]<=a[i]||a[i]==0)); ++j) {
                a[i*p[j]] = p[j];
            }
        }
    }
public:
    CPrime(){
        memset(a, 0, sizeof(a));
        memset(p, 0, sizeof(p));
        primefilter();
    }

    bool isprime(ll n){
        if(n<UPBOUND) return (n>0?!a[n]:0);
        int c = min(3500, pn-1); // 3500个足够支持到1e9
        if(n<p[c]*p[c]) {
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return false;
            }
            return true;
        } else {
            int c = min(1000, pn);
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return false;
            }
            return _isprime(n);
        }
    }

    // 返回质数表第n个质数，p[0]=2, ..., p[n]<UPBOUND
    int nth_prime(int n) {
        return n<pn?p[n]:-32768;
    }

    // 返回n的最小因子
    ll min_divisor(ll n) {
        if(n<UPBOUND) return a[n]?a[n]:n;
        int c = min(3500, pn-1); // 3500个足够支持到1e9
        if(n<p[c]*p[c]) {
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return p[i];
            }
            return n;
        } else {
            // miller_rabin 和 pollard_rho 需要较多的运算
            // 如果有一个小因子不妨先找出来
            int c = min(1000, pn);
            for(int i=0; i<c; i++) {
                if(n%p[i]==0) return p[i];
            }
            return _min_divisor(n);
        }
    }

    // 分解质因数
    vector<pair<ll, int>> factorize(ll n) {
        vector<pair<ll, int>> result;
        while(n!=1) {
            ll p = min_divisor(n);
            int c = 0;
            do {
                n/=p;
                ++c;
            } while(n%p==0);
            result.emplace_back(make_pair(p, c));
        }
        return result;
    }

    // 欧拉函数
    ll phi(ll n) {
        auto factors = factorize(n);
        for(auto [p, c] : factors) {
            n = n / p * (p-1);
        }
        return n;
    }
} Prime;

二分搜索/lower_bound/upper_bound

发表于 2022-05-28 更新于 2024-06-09 分类于算法 Valine：本文字数： 2.3k 阅读时长 ≈ 2 分钟

C++ STL 里实现了两个二分搜索，lower_bound和upper_bound，支持在已经排好序的并且有随机迭代器的容器上进行二分搜索。（事实上map、set、multimap、multiset容器通过成员函数也提供了lower_bound和upper_bound，语意是相同的，实现方式不同）

lower_bound 是返回[b, e)区间上首个大于等于x的元素的迭代器

upper_bound 是返回[b, e)区间上首个大于x的元素的迭代器

下闭上开，和STL里其他地方都是一致的，lower_bound返回的迭代器 p 保证 [p, e) 都是大于等于x的，而upper_bound返回的迭代器q保证[b, q)都是小于等于x的。

STL里的这俩函数基本上不能用在自定义的容器上，因为它们要求容器类型通过typdef定义了各种特定类型，我下面实现了两个替代品，只要求迭代器可以随机访问（即可以加减任意数，随机迭代器可以任意移动，顺序迭代器只能加1减1，链表就只有顺序迭代器），元素有小于运算（我特意把所有的比较都改写成了小于）

// 返回[b,e) 区间上首个大于等于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_lower_bound(Iter b, Iter e, const VT& x)
{
    if(!(*b<x)) return b;
    if(*(e-1)<x) return e;
    while(b<e-2){
        Iter mid=b+(e-b)/2;
        if(*mid<x)
            b=mid;
        else
            e=mid+1;
    }
    return e-1;
}

// 返回[b,e) 区间上首个大于x的元素的迭代器
template<typename Iter, typename VT>
Iter my_upper_bound(Iter b, Iter e, const VT& x)
{
    if(x<*b) return b;
    if(!(x<*(e-1))) return e;
    while(b<e-2){
        Iter mid=b+(e-b)/2;
        if(!(x<*mid))
            b=mid;
        else
            e=mid+1;
    }
    return e-1;
}

二分算法看上去简单，如果不注意是很容易出错的，我觉得主要要注意2点：

1）循环不变性，比如lower_bound，我们找[b,e) 区间上首个大于等于x，在进入循环前我们排除了元素不在[b,e)上的情况，那么在循环内修改b或e的时候就要保证，修改后，要找的元素仍然在[b,e)上，e是开区间的，不要不小心就把元素丢到外面去了。

2）循环能终结，比如我们让b=mid，会不会搜索范围并没有变小呢？一般有几种方式可以调整终结条件，一种就是改while条件，一种就是改mid的计算，mid在偶数大小区间是有两个数可以选择的，mid = b + (e-b)/2 或 mid = b + (e-b+1)/2

有时候序列是降序的怎么办？通过反向迭代器

有时候我们想在一个范围内找满足某个条件的最大值或最小值

// f满足存在一个k值得对于i<k有f(i)=False, 对于i>=k有f(i)=True
// 返回上述的k
template<typename I>
int lower_bound(I b, I e, function<bool(I)> f) {
    if(b >= e) return e;
    while(b < e - 1) {
        auto m = b + (e-1-b) / 2;
        if(!f(m)) b = m + 1;
        else e = m + 1;
    }
    return f(b) ? b : e;
}

相反的，我们可以用lower_bound来实现upper_bound

// f满足存在一个k值得对于i>=k有f(i)=False, 对于i<k有f(i)=True
// 返回上述的k
template<typename I>
int upper_bound(I b, I e, function<bool(I)> f) {
    return lower_bound(b, e, (function<bool(I)>)[&](I i){
        return !f(i);
    });
}

实际使用时写在模板里做了一些改进写成了下面的样子，把b、e的类型写成ll可以避免传参是一个是int一个是unsigned int或者一个ll的情况会编译报错，f的类型写成F而没有用function也是避免要写强制类型转换，使用时可以直接传lambda表达式。

template<typename F>
ll lb(ll b, ll e, F f) {if(b>=e) return e; while(b<e-1) {auto m=b+(e-1-b)/2; if(!f(m)) b=m+1; else e=m+1;} return f(b)?b:e;}
template<typename F>
ll ub(ll b, ll e, F f) {return lb(b, e, [&](ll i){return !f(i);});}

字符串处理/有限状态机

发表于 2022-05-28 更新于 2024-06-09 分类于算法 Valine：本文字数： 2.9k 阅读时长 ≈ 3 分钟

切片

和python中的定义一致，习惯了，比按长度取字串方便，而且负下标也很方便

string slice(const string& s, int b, int e) {
    if(b<0) b += s.size();
    if(e<0) e += s.size();
    return s.substr(b, e-b);
}

去掉字符串前后的空白

python里叫strip，其他语言多叫trim

string strip(const string& s, const string& space=" ") {
    const char* p = &s[0];
    const char* q = &s[0]+s.size();
    for(; p<q; p++) {
        if(space.find(*p) == -1) break;
    }
    if(p<q) q--;
    for(; p<q; q--) {
        if(space.find(*q) == -1) {
            q++;
            break;
        }
    }
    return string(p, q);
}

切开(split)和拼接(join)

支持切开同时strip掉空白字符，比先切开再strip要快，还可以选择是否丢弃切开后空的元素。

vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        if(isdelim) {
            if(e != b || !drop_empty) {
                result.emplace_back(string(&s[b], &s[e]));
            }
            state = 0;
            e = b = i + 1;
        } else if(isspace) {
            if(state == 0) {
                e = b = i + 1;
            }
        } else {
            state = 1;
            e = i + 1;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

string join(vector<string> arr, const string& delim) {
    if(arr.empty()) return "";
    stringstream ss;
    ss << arr[0];
    for(int i=1;i<arr.size();i++) {
        ss << delim << arr[i];
    }
    return ss.str();
}

有限状态机

竞赛中字符串的题目可以考虑先画出状态转换图，然后基于有限状态自动机求解，包括上面的split函数，找不到之前的模板了，我重写的时候就是基于有限状态自动机

刚写出来是下面这样，很多重复代码，一共四个状态，完全就是按状态转移写的，非常清晰。

vector<string> split(const string& s, const string& delim, const string& stripchars="", bool drop_empty=false) {
    vector<string> result;
    int b = 0;
    int e = 0;
    int i = b;
    int state = 0;
    do {
        bool isspace = (stripchars.find(s[i]) != -1);
        bool isdelim = (s[i]=='\0' || delim.find(s[i]) != -1);
        switch(state) {
        case 0:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 1:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 1;
                e = b = i + 1;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        case 2:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        default:
            if(isdelim) {
                if(e != b || !drop_empty) {
                    result.emplace_back(string(&s[b], &s[e]));
                }
                state = 0;
                e = b = i + 1;
            } else if(isspace) {
                state = 3;
            } else {
                state = 2;
                e = i + 1;
            }
            break;
        }
        if(s[i]=='\0') break;
        i++;
    } while(true);
    return result;
}

当然还有可能表面是个字符串的问题，实际上是个动态规划问题或者搜索问题。

Treap（树堆）

发表于 2022-05-24 更新于 2024-06-09 分类于数据结构 Valine：本文字数： 12k 阅读时长 ≈ 10 分钟

最近在LeetCode刷题，又开始复习算法和数据结构，打算写一些东西，记录一些有通用价值的算法和数据结构。

先拿Treap开刀。

什么是Treap？

Treap是一种二叉搜索树（BST），我的本科毕业论文课题就是就是关于二叉搜索树（BST）的研究，Treap在各种操作的效率上不算优秀，全面优秀的是红黑树（RBT），红黑树也是实现起来最复杂的，各种语言的dict，map，set，大概率是基于红黑树实现的，那为什么我讲Treap不讲红黑树呢，因为Treap可能是最易理解且实现起来最简单的且效率还不错的BST，所以经常被用在竞赛中。

Treap支持的操作

1）插入

2）删除

3）查询存在或查询个数

4）查询元素的排名（即元素是第几小，或者说统计小于/大于指定元素的个数）

5）查询第 k 小元素

以上5个操作的平均时间复杂度都是O(logn)，

朴素BST的实现

我们先实现一个朴素的BST，为了简化起见：

1）仅支持3种基本操作，insert，erase，count。（名字按C++ STL容器的命名规则取的）

2）只存key而没有value，像set，而不是map。

3）不能插入重复的key，像set，而不是multiset。

4）没写销毁时的内存释放（那并不困难）

struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(int key):key(key),left(NULL),right(NULL){}
};

class BST {
public:
    void insert(int key) {
        _insert(root, new TreeNode(key));
    }

    int count(int key) const {
        return _count(root, key);
    }

    void erase(int key) {
        return _erase(root, key);
    }

private:
    void _insert(TreeNode* &root, TreeNode* p) {
        if(root == NULL) {
            root = p;
        } else {
            if(p->key == root->key) return;
            if(p->key < root->key) _insert(root->left, p);
            else _insert(root->right, p);
        }
    }

    bool _count(TreeNode* root, int key) const {
        if(root == NULL) return 0;
        if(key == root->key) return 1;
        if(key < root->key) return _count(root->left, key);
        else return _count(root->right, key);
    }

    void _erase(TreeNode* &root, int key) {
        if(root == NULL) return;
        if(key == root->key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            if(left == NULL) {
                delete root;
                root = right; // 因为左子树为空，直接用右子树当根就可以了
            } else if(right == NULL) {
                delete root;
                root = left;
            } else { // 左右子树都不空，把右孩子作为新根
                delete root;
                root = right;
                TreeNode* p = right; // 找到右子树中最小的节点，把左子树接上去
                while(p->left) { 
                    p = p->left;
                }
                p->left = left;
            }
        } else if(key < root->key) {
            _erase(root->left, key);
        } else {
            _erase(root->right, key);
        }
    }

private:
    TreeNode* root = NULL;
};

其中插入insert和查询count都比较简单，主要讲一下erase操作，当删除的是一个非叶子节点，要考虑如何把删除节点的左右子树接上，如果只有左子树或只有右子树，那么直接取代删除节点作为根就可以了，当左右子树都存在时，左右孩子都可以作为新根，这里选择右孩子作为新根，那么要把左子树接上，接到哪里呢，因为整个左子树都key都是小于右子树的，所以可以接在右子树最小的key的left上，而最小的key就是沿left一直下沉到的叶子。

这种删除处理方式虽然是满足BST的性质的，但是显然容易导致树越来越深，因为每次删除操作都会把一棵子树接到叶子节点上，而且总是接到左测最深处，以至于向链表退化，如果改成每次随机选择左右孩子作为新根都会比这好很多。再来看插入操作，只要升序或降序插入，就相当于一直朝着BST的最右或者最左节点插入，这会导致BST退化成链表，那么它的插入、删除、查询等操作的时间复杂度将退化成O(n)，这是不能接受的。各种不同的BST，其实都是通过增加约束条件，使用额外的维护操作维护约束的满足，来减小BST的最大深度，把平均甚至最坏的深度维持在O(logn)。

Treap是如何克服上述朴素BST的问题的呢？

Treap由二叉树和二叉堆组合形成，名字也因此为 tree 和 heap 的组合，除了记录key之外，它还额外记录一个priority来维持最大堆的性质，即父节点的priority大于等于两个子节点的priority，priority一般随机生成，正因为引入了最大堆的约束，和随机的priority，这棵树就不会在某种精心构造的插入删除序列下退化得很深，期望的深度是O(logn)，插入、删除、查询的期望复杂度也是O(logn)，最坏情况O(n)，依赖于priority的生成，因为priority是随机的所以最坏情况基本不会发生。

那么如何维护最大堆约束的满足呢？

我们需要引入旋转操作，分左旋和右旋，如图所示：

容易看出旋转是不破坏BST性质的，对root右旋用文字描述就是，把root的左孩子作为新根，左孩子的右子树作为旧根的左子树，旧根作为新根的右子树，说起来绕来绕去不好理解，右旋就是把左孩子拎起来成为根，左旋就是把右孩子拎起来成为根，子树的切换是要维持BST性质，想搞错也不容易。

有了不破坏BST性质的旋转操作我们就可以维护堆的性质了，如果左孩子的priority比根大，我们就右旋，让左孩子成为根，如果右孩子的priority比根大，我们就左旋，让右孩子成为根。

Treap的实现

struct TreeNode {
    int key;
    int priority;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(int key):key(key),priority(rand()),left(NULL),right(NULL){}
};

class Treap {
public:
    void insert(int key) {
        _insert(root, new TreeNode(key));
    }

    int count(int key) const {
        return _count(root, key);
    }

    void erase(int key) {
        return _erase(root, key);
    }

private:
    void lrotate(TreeNode* &root) {
        TreeNode* right = root->right;
        //if(right==NULL) return; // 右子树为空不能左旋
        TreeNode* rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        root = right;
    }

    void rrotate(TreeNode* &root) {
        TreeNode* left = root->left;
        //if(left==NULL) return; // 左子树为空不能右旋
        TreeNode* leftright = left->right;
        root->left = leftright;
        left->right = root;
        root = left;   
    }

    void _insert(TreeNode* &root, TreeNode* p) {
        if(root == NULL) {
            root = p;
        } else {
            if(p->key == root->key) return;
            if(p->key < root->key) {
                _insert(root->left, p);
                if(root->left->priority > root->priority){
                    rrotate(root);
                }
            }
            else {
                _insert(root->right, p);
                if(root->right->priority > root->priority){
                    lrotate(root);
                }
            }
        }
    }

    int _count(TreeNode* root, int key) const {
        if(root == NULL) return 0;
        if(key == root->key) return 1;
        if(key < root->key) return _count(root->left, key);
        else return _count(root->right, key);
    }

    void _erase(TreeNode* &root, int key) {
        if(root == NULL) return;
        if(key == root->key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            if(left == NULL) {
                delete root;
                root = right; // 因为左子树为空，直接用右子树当根就可以了
            } else if(right == NULL) {
                delete root;
                root = left;
            } else {
                if(left->priority < right->priority) {
                    rrotate(root); // 把优先级大的孩子转成根
                    _erase(root->right, key);
                } else {
                    lrotate(root);
                    _erase(root->left, key);
                }
            }
        } else if(key < root->key) {
            _erase(root->left, key);
        } else {
            _erase(root->right, key);
        }
    }

private:
    TreeNode* root = NULL;
};

先看插入操作，比朴素BST仅仅多了递归insert后的判断旋转，我们只需关注当前root是否需要旋转，因为这是在递归插入的回退过程中进行的旋转，事实上每次插入都是发生在叶子的，在递归插入回退的过程中新插入的节点会逐层地通过旋转被上推到合适的高度。

再看删除操作，甚至比朴素BST很简洁，在找到需要删除的节点后，我们总是先通过旋转把它下沉，直到它只有一个孩子或者没有孩子，然后再删掉它把孩子接上来。

Treap的完整实现

下面增加了销毁代码，并对动态空间申请释放做了优化，支持插入重复元素，并且实现了另外两个操作：

1）查询元素的排名（即元素是第几小，或者说有多少元素小于指定元素）

2）查询第 k 小元素

#include <iostream>
#include <cassert>
#include <vector>
#include <queue>

using namespace std;

namespace detail {

template <typename T>
struct TreeNode {
    T key;
    int priority;
    int size;
    TreeNode* left;
    TreeNode* right;

    TreeNode():TreeNode(0){}
    TreeNode(T key, int multi=1):key(key),priority(rand()),size(multi),left(NULL),right(NULL){}
};

template <typename T>
class TreeNodePool {
    int batchsize = 1024;
    vector<char*> memchunks;
    queue<char*> blocks;
public:
    ~TreeNodePool() {
        for(int i=0;i<memchunks.size();i++) {
            free(memchunks[i]);
        }
    }

    TreeNode<T>* create(int key, int multi=1) {
        if(blocks.empty()) {
            char* p = (char*)malloc(sizeof(TreeNode<T>)*batchsize);
            memchunks.emplace_back(p);
            for(int i=0;i<batchsize;i++) {
                blocks.push(p+sizeof(TreeNode<T>)*i);
            }
            batchsize *= 2;
        }
        char* p = blocks.front(); blocks.pop();
        return new (p)TreeNode<T>(key, multi);
    }

    void release(TreeNode<T>* p) {
        blocks.push((char*)p);
    }
};
} // namespace detail

template<typename T>
class Treap {
public:
    // key: 插入的元素
    // multi: 插入元素的重数
    int insert(T key, int multi=1) {
        return _insert(root, create_tree_node(key, multi));
    }

    // 返回等于key的元素个数
    int count(T key) const {
        return _count(root, key);
    }

    // key: 删除的元素
    // all: 如果有重复元素是否删除所有
    void erase(T key, bool all=false) {
        _erase(root, key, all);
    }

    // 返回树中元素个数
    int size() const {
        return _size(root);
    }

    // 返回第n小元素，从0起算
    T nth_element(int n) {
        assert(0<=n && n<size());
        return _nth_element(root, n)->key;
    }

    // 返回小于key的元素个数
    int cnt_less(T key) const {
        return _cnt_less(root, key);
    }

    // 返回小于等于key的元素个数
    int cnt_lesseq(T key) const {
        return cnt_less(key) + count(key);
    }

    // 返回大于key的元素个数
    int cnt_greater(T key) {
        return size() - cnt_lesseq(key);
    }

private:
    detail::TreeNode<T>* create_tree_node(T key, int multi=1) {
        return pool.create(key, multi);
    }
    void release_tree_node(detail::TreeNode<T>* root) {
        pool.release(root);
    }

    static int _size(detail::TreeNode<T>* root) {
        return (root != NULL ? root->size : 0);
    }
    // 返回root子树的size减去左右子树的size
    static int _count(detail::TreeNode<T>* root) {
        if(root == NULL) return 0;
        return _size(root) - _size(root->left) - _size(root->right);
    }

    static void lrotate(detail::TreeNode<T>* &root) {
        auto right = root->right;
        assert(right!=NULL);
        auto rightleft = right->left;
        root->right = rightleft;
        right->left = root;
        int root_size = root->size;
        root->size += _size(rightleft) - _size(right);
        right->size = root_size;
        root = right;
    }

    static void rrotate(detail::TreeNode<T>* &root) {
        auto left = root->left;
        assert(left!=NULL);
        auto leftright = left->right;
        root->left = leftright;
        left->right = root;
        int root_size = root->size;
        root->size += _size(leftright) - _size(left);
        left->size = root_size;
        root = left;   
    }

    int _insert(detail::TreeNode<T>* &root, detail::TreeNode<T>* p) {
        if(root == NULL) {
            root = p;
            return p->size;
        } else {
            if(p->key < root->key) {
                int r = _insert(root->left, p);
                root->size += r;
                if(root->left->priority > root->priority){
                    rrotate(root);
                }
                return r;
            } else if(root->key < p->key) {
                int r = _insert(root->right, p);
                root->size += r;
                if(root->right->priority > root->priority){
                    lrotate(root);
                }
                return r;
            } else {
                root->size += p->size;
                release_tree_node(p);
                return p->size;
            }
        }
    }

    static int _count(detail::TreeNode<T>* root, T key) {
        if(root == NULL) return 0;
        if(key < root->key) return _count(root->left, key);
        else if(root->key < key) return _count(root->right, key);
        else return _count(root);
    }

    int _erase(detail::TreeNode<T>* &root, T key, bool all) {
        if(root == NULL) return 0;
        if(key == root->key) {
            auto left = root->left;
            auto right = root->right;
            if(left == NULL) {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    release_tree_node(root);
                    root = right;
                    return root_count;
                }
            } else if(right == NULL) {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    release_tree_node(root);
                    root = left;
                    return root_count;
                }
            } else {
                int root_count = _count(root);
                if(!all && root_count > 1) {
                    root->size--;
                    return 1;
                } else {
                    int r = 0;
                    if(left->priority < right->priority) {
                        lrotate(root); // 把优先级大的孩子转成根
                        r = _erase(root->left, key, all);
                    } else {
                        rrotate(root);
                        r = _erase(root->right, key, all);
                    }
                    root->size -= r;
                    return r;
                }
            }
        } else if(key < root->key) {
            int r = _erase(root->left, key, all);
            root->size -= r;
            return r;
        } else {
            int r = _erase(root->right, key, all);
            root->size -= r;
            return r;
        }
    }

    static int _cnt_less(detail::TreeNode<T>* root, T key) {
        if(root == NULL) return 0;
        if(key < root->key) return _cnt_less(root->left, key);
        else if(root->key < key) return _size(root) - _size(root->right) + _cnt_less(root->right, key);
        else return _size(root->left);
    }

    static detail::TreeNode<T>* _nth_element(detail::TreeNode<T>* root, int n) {
        if(root == NULL) return NULL;
        int left_size = _size(root->left);
        int right_size = _size(root->right);
        if(n < left_size) return _nth_element(root->left, n);
        else if(n < _size(root) - right_size) return root;
        else return _nth_element(root->right, n - (_size(root) - right_size));
    }

private:
    detail::TreeNodePool<T> pool;
    detail::TreeNode<T>* root = NULL;
};

linux为常用压缩解压命令创建别名

发表于 2022-05-21 更新于 2024-06-09 分类于随笔 Valine：本文字数： 691 阅读时长 ≈ 1 分钟

# .tar.gz / .tgz 
alias tgzc='_tgzc(){ tar -zcvf `basename $1`.tar.gz $1; };_tgzc'
alias tgzx='tar -zxvf'
# .tar.bz2 / .tbz2
alias tbz2c='_tbz2c(){ tar -jcvf `basename $1`.tar.bz2 $1; };_tbz2c'
alias tbz2x='tar -jxvf'
# .tar.xz / .txz
alias txzc='_txzc(){ tar -Jcvf `basename $1`.tar.xz $1; };_txzc'
alias txzx='tar -Jxvf'
# .7z
alias 7zc='_7zc(){ 7za a -r `basename $1`.7z $1; };_7zc'
alias 7zx='_7zx(){ 7za x $1 -r -o./; };_7zx'

统一了不同格式的压缩解压命令，省略了参数，只支持最常用的情况，即：

· 压缩当前路径下的指定目录形成同名的压缩文件

· 提取当前路径下的指定压缩文件的内容到当前路径

压缩用法，压缩当前路径下的 foo 目录

tgzc foo

tgzc foo/

1	tgzc ./foo

都可以在当前目录生成 foo.tar.gz

解压用法，解压当前路径下的 foo.7z 文件到当前路径下

1	7zx foo.7z

linux上升级gcc/g++

发表于 2022-05-21 更新于 2024-06-09 分类于运维 Valine：本文字数： 1.3k 阅读时长 ≈ 1 分钟

Ubuntu

添加源，默认的稳定源里最新只有gcc8，如果需要更高的版本需要添加这个测试源，这一步不是必须做，可以先看看默认的源里是否已经有了你想要的版本

1	sudo add-apt-repository ppa:ubuntu-toolchain-r/test

更新软件列表

1	sudo apt-get update

安装想要升级的gcc/g++版本

1	sudo apt-get install gcc-9 g++-9

查看目前存在的版本

1 2	sudo updatedb && sudo ldconfig locate gcc \| grep -E "/usr/bin/gcc-[0-9]"

通过update-alternatives切换默认版本（本质是修改软连接，最后的数字是优先级，优先级高的自动为默认版本）

sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-7 20
sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-9 50

sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-7 20
sudo update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-9 50

现在就升级好了，可以通过命令查看

1 2	gcc --version g++ --version

BTW：

之后可以随时通过

1	sudo update-alternatives --config gcc

手动切换默认版本

而删除一个版本使用下面的命令

1	sudo update-alternatives --remove gcc /usr/bin/gcc-9

CentOS

安装scl源

1	yum install -y centos-release-scl scl-utils-build

查看可以安装的gcc版本

1	yum list all --enablerepo='centos-sclo-rh' \| grep gcc

安装 devtoolset-9

1	yum install -y devtoolset-9-gcc.x86_64 devtoolset-9-gcc-c++.x86_64 devtoolset-9-gcc-gdb-plugin.x86_64

开启一个指定gcc/g++版本的bash

1	scl enable devtoolset-9 bash

可以在/etc/profile 中加入，这样每次登录就自动切换到gcc-9的环境了

指定cmake时的gcc版本

执行cmake生成Makefile时，cmake会去发现系统上的gcc

我实际使用时，在centos上系统存在gcc时，通过

1	scl enable devtoolset-9 bash

切换gcc版本后，使用cmake生成Makefile会出现仍然使用系统默认gcc的情况

解决方式：切换gcc版本后指定CC和CXX环境变量指向需要使用的gcc和g++，再执行cmake

1 2	export CC=`which gcc` export CXX=`which g++`

linux目录结构介绍

发表于 2022-05-11 更新于 2024-06-09 分类于随笔 Valine：本文字数： 2.1k 阅读时长 ≈ 2 分钟

/bin 存放基础命令的可执行文件和符号连接，包括cat, cp, ls, touch, rm等

/sbin 存放超级用户使用的基础的管理程序，包括ifup, iptables, mkfs, route, swapon等

/usr Unix Software Resource的缩写，也就是系统软件资源所放置的目录，全部软件都安装在这里
/usr/bin 存放很多应用程序的可执行文件，包括akw, vim, gcc, go, cmake等
/usr/local/bin 存放安装出来的可执行文件，包括ipython, jupyter-notebook, pip, wheel等
/usr/sbin 存放一些非核心的管理程序和一些安装出来的daemon程序，包括useradd, nginx, netplan, mysqld, sshd等
/usr/include Linux下开发和编译应用程序需要的头文件
/usr/lib 动态链接共享库和静态档案库目录
/usr/src 源代码目录
/usr/doc 文档目录
/usr/man 帮助文档目录

/var variable的缩写，包含可变的数据文件
/var/log/ 各种程序的日志文件
/var/www/ nginx网站目录，相当于nginx的数据文件
/var/lib/ 各种程序运行时会改变的数据文件
/var/lib/docker/ docker的镜像和容器数据
/var/lib/mysql/ mysql数据库的数据
/var/lib/mongodb/ mongodb数据库的数据

/etc 包含所有系统管理和维护方面的配置文件
/etc/hosts 域名解析配置
/etc/resolv.conf 域名解析服务器配置
/etc/init.d/ 自启动脚本，详见配置Linux开机启动脚本（基于initd）
/etc/rc?.d/ 自启动脚本的软连接，?表示系统的运行级
/etc/profile 所有用户登录Shell时执行
/etc/profile.d/ 所有用户登录Shell时遍历目录下的脚本执行
/etc/issue Linux版本信息
/etc/sudoers 配置允许sudo的用户
/etc/passwd 用户列表 username:原密码占位符x:uid:gid:描述性信息:家目录:默认Shell
/etc/apt/sources.list apt软件源配置，详见替换Ubuntu 18.04软件源
/etc/network/interfaces 网卡配置文件
/etc/netplan/*.yaml 网卡配置文件
/etc/fstab 系统启动时自动执行的挂载路径，也是mount -a时挂载的路径，详见 Linux NFS共享目录配置及开机自动挂载
/etc/exports 配置通过nfs共享的目录，详见 Linux NFS共享目录配置及开机自动挂载
/etc/samba/smb.conf 配置通过samba共享的目录
/etc/systemd/system/*.service 自启动的服务配置文件的符号连接，详见配置Linux开机启动脚本（基于systemd）
/etc/docker/daemon.json docker配置文件
/etc/nginx/nginx.conf /etc/nginx/sites-enabled/default nginx配置文件，详见 nginx配置
/etc/mysql/my.cnf /etc/mysql/mysql.conf.d/mysqld.cnf mysql配置文件
/etc/redis/redis.conf redis配置文件

/lib 包含系统引导和在root用户执行命令时候所必需用到的共享库

/root root用户的家目录

/opt 用户级的程序目录，自己下载解压的软件可以放在这个目录下，然后将可执行文件的符号连接创建到 /usr/local/bin

/boot 目录存放系统核心文件以及启动时必须读取的文件，包括Linux内核的二进制映像

/tmp 临时文件目录

/mnt 该目录是默认的文件系统临时装载点

/media 挂在多媒体设备的目录，如默认情况下软盘、光盘、U盘设备都挂在在此目录

/dev 目录保存着外部设备代码的文件，这些文件比较特殊，实际上它们都指向所代表的外围设备，如终端、磁盘驱动器、光驱、打印机等。

/proc 进程文件系统proc的根目录，其中的部分文件分别对应正在运行的进程，可用于访问当前进程的地址空间。它是一个非常特殊的虚拟文件系统，其中并不包含“实际的”文件，而是可用以引用当前运行系统的系统信息，如CPU、内存、运行时间、软件配置以及硬件配置的信息，这些信息是在内存中由系统自己产生的。

/sys 是一个类似于proc文件系统的特殊文件系统，用于将系统中的设备组织成层次结构，并向用户模式程序提供详细的内核数据结构信息。其实，就是在用户态可以通过对sys文件系统的访问，来看内核态的一些驱动或者设备等。

/run 目录中存放的是自系统启动以来描述系统信息的文件。比较常见的用途是daemon进程将自己的pid保存到这个目录。标准要求这个文件夹中的文件必须是在系统启动的时候清空，以便建立新的文件。