Treap的区间操作 NOI2005维护序列

Fhq-Treap的序列操作

- Fhq-Treap的序列操作
  - - 节点
    - 划分
    - 合并
    - 笛卡尔树
      - 性质
      - 构造
    - 插入
    - 删除
    - 求和
    - 最大子列和
    - 修改
    - 翻转

比如NOI2005 维护序列, 这道题应该如何应用Fhq-Treap来维护呢?1

节点

我们还是采用指针式的Fhq-Treap. 为了可以把update(), spread(), assign(), reverse()等函数作为先无视这些成员函数, 我先谢了struct声明, 并申请了null假空指针, 在继续定义struct. 一个随机数函数, 但是效果一般…

inline int random(){
    static int seed=; //seed可以随便取
    return seed=int(seed*LL%);
}
struct Treap;
Treap * null, * work;
struct Treap{
    Treap * left, * right;
    int value, priority, size;
    int sum, msum, lsum, rsum;// 树和, 最大子序列和, 左最大子序列和, 右最大子序列和
    int rev, ass;// 区间翻转标记, 赋值标记
    Treap(){// 此函数只是给null用的
        size = ;
        sum = ;
        rev = ;
        ass = INF;
        sum = ;
        msum = lsum = rsum = -INF;
    };
    Treap(Treap * l, Treap * r, int v, int p): left(l), right(r), value(v), priority(p){
        rev = ;
        ass = INF;
        sum = msum = lsum = rsum = v;
        size = ;
    }
    void update(){
        size = left->size + right->size + ;
        sum = left->sum + right->sum + value;

        msum = max(left->rsum + value + right->lsum, max(left->msum, right->msum));
        msum = max(msum, max(left->rsum + value, right->lsum + value));
        msum = max(msum, value);

        lsum = max(left->lsum, max(left->sum + value, left->sum + value + right->lsum));
        rsum = max(right->rsum, max(value + right->sum, left->rsum + value + right->sum));
    }
    void reverse(){
        if(this != null){
            rev ^= ;
            swap(left, right);
            swap(lsum, rsum);
        }
    }
    void assign(int c){
        if(this != null){
            rev = ;
            value = c;
            sum = size * c;
            ass = c;
            lsum = rsum = msum = max(c, sum);
        }
    }
    void spread(){// 下传标记
        if(this == null){
            return;
        }
        if(ass != INF){
            left->assign(ass);
            right->assign(ass);
            rev = ;
            ass = INF;
        }
        if(rev){
            rev = ;
            left->reverse();
            right->reverse();
        }
    }
};

划分

我们之前做普通平衡树使用的划分函数是根据值的大小来划分的, 这里我们采用把前k个元素分离出来的划分函数.

typedef pair<Treap *, Treap *> pTT;
pTT split(Treap * root, int k){
    if(root == null){
        return make_pair(null, null);
    }
    root->spread();
    pTT result;
    if(k <= root->left->size){
        result = split(root->left, k);
        root->left = result.second;
        root->update();
        result.second = root;
    }
    else{
        result = split(root->right, k - root->left->size - );
        root->right = result.first;
        root->update();
        result.first = root;
    }
    return result;
}

这份代码比较好理解, 这种划分方式, 很像在树上找第K个大的数字.

合并

Treap * merge(Treap * left, Treap * right){
    left->spread(), right->spread();
    if(left == null){
        return right;
    }
    if(right == null){
        return left;
    }
    if(left->priority < right->priority){
        left->right = merge(left->right, right);
        left->update();
        return left;
    }
    else{
        right->left = merge(left, right->left);
        right->update();
        return right;
    }
}

合并操作也很简单.

为了能够让Fhq-Treap能够维护序列, 我们需要知道==笛卡尔树(Cartesian Tree)==的知识.

笛卡尔树

笛卡尔树是一种同时满足二叉搜索树和堆的性质的数据结构. 可以在一个数组上构造出来(时间复杂度可以达到 O(n) O ( n ) ). 树中节点有几个属性, key(节点元素的大小, 优先级priority), index(节点在元素组中的索引), left(左子节点), right(右子节点), parent(父节点).

性质

树中的元素满足二叉搜索树性质, 树的中序遍历得到的序列为原数组序列;
树中节点满足堆性质, 节点的==key==值要大于其左右子节点的key值.

构造

要求在给定的数组的基础上构造一颗笛卡尔树, 这可以在 O(n) O ( n ) 的时间内完成. 其具体思路为:

当按照index从1到n(或者从0到n - 1)的顺序将数组中的每个元素插入到笛卡尔树中时, 当前要被插入的元素的index值最大, 因此根据二叉搜索树的性质, 需要在当前已经完成的笛卡尔树的根的右子树中进行搜索.

由于笛卡尔树要满足堆的性质(以大根堆为例), 父节点的key值要大于子节点的key值, 所以沿着树根的右子树往下走, 直到遇到的节点的key值小于等于当前要插入节点的key值.

此时, 便找到了当前节点需要插入的位置, 记为 P P . 此时PP下方的节点的key值肯定小于当前要插入的节点的key, index也小于当前要插入的节点的index.

所以在讲当前节点插入到P的位置后, 把以P为根的子树挂到当前已经插入的节点的左子树上.

实际实现时, 可采用栈. 栈中保存当前树中从root开始的右子节点链, root在栈底.

插入新元素的时候, 从树的右子链的最末尾从下往上查找, 直到找到第一个满足堆性质的节点(即找到的节点的key值大于当前需要插入的节点). 用栈来实现就是从栈顶不断弹出元素, 直到栈顶的元素的key大于当前节点的key, 然后将该节点入栈, 同时将最后被弹出的节点的parent指向该节点, 以及该节点的左子节点指向最后弹出的节点.

Treap * build(){
    int num;
    Treap * last, * t;
    stack<Treap *> s;
    for(int i = ; i < tot; ++i){
        scanf("%d", &num);
        if(freepool.empty()){
            t = new Treap(null, null, num, Random());
        }
        else{
            t = freepool.front();
            freepool.pop();
            t->set(num, Random());
        }
        last = null;
        while(s.size() && s.top()->priority > t->priority){
            last = s.top();
            s.pop();
            last->update();
        }
        if(s.size()){
            s.top()->right = t;
        }
        t->left = last;
        s.push(t);
    }
    while(s.size() > ){
        s.top()->update();
        s.pop();
    }
    s.top()->update();
    return s.top();
}

我开始的时候在想, 如何在分裂中保持序列的index顺序呢? 想到的方法只是在加一个域, 但是实际上, 在我们笛卡尔建树的时候, 我们是认为序列右的元素“大于”序列左的元素的. 经过一次中序遍历, 得到的序列就是原序列.

但是为什么这样就能够用Treap维护序列了呢?

为什么我们可以在不断的split, merge操作中, 维持序列的先后关系不变呢?

因为我们的split, merge是不改变树中元素的大小关系的.

想一下, split只是把树中前K个元素分离出来, 并不改变序列的前后次序.

merge只是把先后次序确定的两个序列合并, 也不会错乱整体序列的先后次序.

不理解的小伙伴可以自己手写我就是自己手动画图建树才理解的一个序列, 根据笛卡尔建树规则建一个树, priority值自己想几个, 不要太大.

插入

例如在第pos个元素后插入tot个元素. 我们先根据着tot个元素, 使用建一颗笛卡尔树.

在从原来的树中分离出前pos个元素, 在来两次合并即可.

void insert(){
    scanf("%d%d", &pos, &tot);
    Treap * root = build();
    pTT result = split(work, pos);
    work = merge(merge(result.first, root), result.second);
}

删除

例如删除从第pos个元素开始, 连续的tot个元素.

我们先把pos - 1个元素分离出来, 得到两个子树left, right, 在从right子树中分离tot个元素.

这样就得到了3颗树, 也就是3个序列, 只合并两侧的两颗树即可. 最后在递归删除中间的树.

void del(Treap * root){
    if(root == null){
        return;
    }
    del(root->left);
    del(root->right);
    delete root;
}
void remove(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    del(right.first);
    work = merge(left.first, right.second);
}

求和

我们只需要给每个节点维护一个sum变量, 代表着以此节点为根的子树的权值和.

以此节点为根的子树和 ≡ 左儿子为根的子树和 + 右儿子为根的子树和 + 此节点的权值.

我们只需要在每次split, merge的时候进行一次update就可以维护整颗树的sum值了.

对于例如求从第pos个元素开始, 连续tot个元素的权值和这样的问题, 我们可以通过两次split得到要操作的序列,

在直接查询这颗树的权值和即可.

void getSum(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    printf("%d\n", right.first->sum);
    work = merge(left.first, merge(right.first, right.second));
}

最大子列和

这个和线段树的问题很像, 但细节处略有差别, 主要是要注意不知右left, right, 还有当前根节点. 这里我不在细述.

主要是当前区间的最大子列和, 要么在左节点中, 要么在有节点中, 要么就横跨左右节点.

修改

例如把从第pos个元素开始, 连续的tot个元素的值都改为c.

我们还是先把要操作的区间经过两次分离操作独立出来, 然后在修改这个区间, 要注意的是, 这里我们使用Lazy-tag的思想, 和线段树一样, 先修改根节点, 并给根节点打标记, 在要访问子节点的时候, 在下传标记这里可以看split, merge函数中spead()使用的时机.

注意我们要保证, 但访问到一个节点时, 它的祖先没有任何标记.

同时要理解, 如果一个节点有标记, 那说明这个节点的修改已经完成, 只需要在修改子节点即可.

void assign(){
    scanf("%d%d%d", &pos, &tot, &c);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    right.first->assign(c);
    work = merge(left.first, merge(right.first, right.second));
}

这时候, 我们需要看这个assign()成员函数. 它会根据c的值, 来修改调用它的节点.

翻转

例如把从第pos个元素开始, 连续的tot个元素的值翻转.

还是先把要操作的区间独立出来, 然后把这颗树的左右儿子交换, 并打上交换标记(意思是当前节点的孩子还需要继续翻转).

void reverse(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    right.first->reverse();
    work = merge(left.first, merge(right.first, right.second));
}

最后的两个操作要注意下传标记时的时机, 以及如何操作, 主要是理解延迟标记思想.

最后附上NOI2005 维护序列的代码, 这份代码没有使用内存池技术, 没有快速读入挂. 不开O2在洛谷会TLE…在Vijos能AC.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
const int INF = ;
int pos, tot, c;
struct Treap;
Treap * null, * work;
struct Treap{
    Treap * left, * right;
    int value, priority, size;
    int sum, msum, lsum, rsum;// 树和, 最大子序列和, 左最大子序列和, 右最大子序列和
    int rev, ass;// 区间翻转标记, 赋值标记
    Treap(){
        size = ;
        sum = ;
        rev = ;
        ass = INF;
        sum = ;
        msum = lsum = rsum = -INF;
    };
    Treap(Treap * l, Treap * r, int v, int p): left(l), right(r), value(v), priority(p){
        rev = ;
        ass = INF;
        sum = msum = lsum = rsum = v;
        size = ;
    }
    void update(){
        size = left->size + right->size + ;
        sum = left->sum + right->sum + value;
        msum = max(left->rsum + value + right->lsum, max(left->msum, right->msum));
        msum = max(msum, max(left->rsum + value, right->lsum + value));
        msum = max(msum, value);
        lsum = max(left->lsum, max(left->sum + value, left->sum + value + right->lsum));
        rsum = max(right->rsum, max(value + right->sum, left->rsum + value + right->sum));
    }
    void reverse(){
        if(this != null){
            rev ^= ;
            swap(left, right);
            swap(lsum, rsum);
        }
    }
    void assign(int c){
        if(this != null){
            rev = ;
            value = c;
            sum = size * c;
            ass = c;
            lsum = rsum = msum = max(c, sum);
        }
    }
    void spread(){
        if(this == null){
            return;
        }
        if(ass != INF){
            left->assign(ass);
            right->assign(ass);
            rev = ;
            ass = INF;
        }
        if(rev){
            rev = ;
            left->reverse();
            right->reverse();
        }
    }
};
typedef pair<Treap *, Treap *> pTT;
pTT split(Treap * root, int k){
    if(root == null){
        return make_pair(null, null);
    }
    root->spread();
    pTT result;
    if(k <= root->left->size){
        result = split(root->left, k);
        root->left = result.second;
        root->update();
        result.second = root;
    }
    else{
        result = split(root->right, k - root->left->size - );
        root->right = result.first;
        root->update();
        result.first = root;
    }
    return result;
}
Treap * merge(Treap * left, Treap * right){
    left->spread(), right->spread();
    if(left == null){
        return right;
    }
    if(right == null){
        return left;
    }
    if(left->priority < right->priority){
        left->right = merge(left->right, right);
        left->update();
        return left;
    }
    else{
        right->left = merge(left, right->left);
        right->update();
        return right;
    }
}
Treap * build(){
    int num;
    Treap * last, * t;
    stack<Treap *> s;
    for(int i = ; i < tot; ++i){
        scanf("%d", &num);
        t = new Treap(null, null, num, rand());
        last = null;
        while(s.size() && s.top()->priority > t->priority){
            last = s.top();
            s.pop();
            last->update();
        }
        if(s.size()){
            s.top()->right = t;
        }
        t->left = last;
        s.push(t);
    }
    while(s.size() > ){
        s.top()->update();
        s.pop();
    }
    s.top()->update();
    return s.top();
}
void insert(){
    scanf("%d%d", &pos, &tot);
    Treap * root = build();
    pTT result = split(work, pos);
    work = merge(merge(result.first, root), result.second);
}
void del(Treap * root){
    if(root == null){
        return;
    }
    del(root->left);
    del(root->right);
    delete root;
}
void remove(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    del(right.first);
    work = merge(left.first, right.second);
}
void assign(){
    scanf("%d%d%d", &pos, &tot, &c);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    right.first->assign(c);
    work = merge(left.first, merge(right.first, right.second));
}
void getSum(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    printf("%d\n", right.first->sum);
    work = merge(left.first, merge(right.first, right.second));
}
void reverse(){
    scanf("%d%d", &pos, &tot);
    pTT left = split(work, pos - );
    pTT right = split(left.second, tot);
    right.first->reverse();
    work = merge(left.first, merge(right.first, right.second));
}
int main(){
    null = new Treap(), work = null;
    int m;
    scanf("%d%d", &tot, &m);
    char cmd[];
    work = build();
    while(m--){
        scanf("%s", cmd);
        switch(cmd[]){
            case 'I':
                insert();
                break;
            case 'D':
                remove();
                break;
            case 'M':
                if(cmd[] == 'K'){
                    assign();
                }
                else{
                    printf("%d\n", work->msum);
                }
                break;
            case 'G':
                getSum();
                break;
            case 'R':
                reverse();
                break;
        }
    }
    return 0;
}

很多情况下, 树和区间是同义, 下文中不在严格区分. ↩

Treap的区间操作 NOI2005维护序列

Fhq-Treap的序列操作

节点

划分

合并

笛卡尔树

性质

构造

插入

删除

求和

最大子列和

修改

翻转

继续阅读

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

codeforces 838D D. Airplane Arrangements 构造法推公式

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

HDU Reorder the Books

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

hdu 4741 Save Labman No.004（计算几何） Save Labman No.004

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器