【数据结构】平衡树之FHQ-Treap

CNS_5t0_0r2 · 2024-07-17 19:11:18 · 算法·理论

请保证你有 BST 的基础再阅读本文。

本文只讲解 FHQ-Treap（我最喜欢用的平衡树，~~主要是觉得 Splay 代码太难写所以不想写了~~）。

【0】引入

众所周知，BST 在极端情况下会退化成单次操作 O(n)，总复杂度 O(n ^ 2)，但在随机数据的情况下单次为 O(\log n)。这启发我们：在没有随机的情况下创造随机。

所以，可以对每个点随机赋一个权值。但这还不够，我们还得让节点按照随机权值排一个序（这种操作并没有破坏 BST 的性质）。Treap 的实现方法就是让随机权值满足堆的性质（下文中的 FHQ-Treap 满足大根堆的性质）来实现单次复杂度 O(\log n)。

【1】FHQ-Treap 维护集合

【1.1】FHQ-Treap 的两个基本操作：`split` 和 `merge`

无论是维护集合还是维护序列，FHQ-Treap 都是基于这两个操作实现的，这其中不需要旋转，所以 FHQ-Treap 又叫“无旋 Treap”。

【1.1.1】`split` 操作

split 有两种：按排名分裂和按数值分裂。维护集合用到的是后者。

按数值分裂的定义：split(u,x,&L,&R) 的定义是将以 u 为根的子树分裂成值不超过和超过 x 的两棵子树并返回两棵子树的根 L,R。

分类讨论。当当前根 u 的权值不大于 x 时，显然整个左子树都应该分到分裂后的左子树，则 L = u。进入右子树时，会把右子树也分裂成两个子树。其中不大于 x 的子树（根设为 v）应该和 u 分裂后的左子树包含在同一个子树中，所以 v 应作为 u 的右儿子，即在进入右子树的时候传入 t[u].rc 的指针。

反过来同理。

这样分裂出来的两个子树显然也满足 FHQ-Treap 的性质（即随机权值满足大根堆的性质），因为任意两节点如果分裂到同一棵子树中，祖先-子孙关系不变。

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x，右子树所有节点权值 > x
    if(u == 0){
        L = R = 0;
        return;
    }
    if(t[u].val <= x){
        L = u;
        split(t[u].rc,x,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}

【1.1.2】`merge` 操作

merge 操作是 split 操作的逆操作，所以 merge 操作要求左子树的最大值小于右子树的最小值。在此基础上，我们要保证随机权值满足堆的性质。

设需要合并的两棵子树的根为 u 和 v，如果 u 的随机权值大于 v，那么 v 应该在 u 的右子树中。但是这会挤占原来 u 的右子节点的位置，所以应该合并 u 的右子树和以 v 为根的子树，并把这棵合并后的子树作为 u 的右子树，合并后的根即为 u。

反过来同理。

/*合并的前提条件：
    1. 保证 t[u].val <= t[v].val
    2. 一个子树中的最大值小于另一个子树中的最小值
*/
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根 
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

以下是模版题的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct node{
    int val,pri;
    int lc,rc;
    int siz;
} t[N];
int node_cnt,root;

void push_up(int u){
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x，右子树所有节点权值 > x
    if(u == 0){
        L = R = 0;
        return;
    }
    if(t[u].val <= x){
        L = u;
        split(t[u].rc,x,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}
/*合并的前提条件：
    1. 保证 t[u].val <= t[v].val
    2. 一个子树中的最大值小于另一个子树中的最小值
*/
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根 
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

void new_node(int x){
    t[++node_cnt] = (node){x,rand() * rand(),0,0,1};
}
void insert(int x){
    int u,v;
    split(root,x,u,v);
    new_node(x);
    root = merge(merge(u,node_cnt),v);
}
void remove(int x){
    int u,v,w;
    split(root,x,u,v);//分裂成 <= x 的子树和 > x 的子树 
    split(u,x - 1,u,w);//分裂成 < x 的子树和 == x 的子树 
    w = merge(t[w].lc,t[w].rc);//合并 w（== x 的子树） 的左右子树 ，相当于删除了一个 x
    root = merge(merge(u,w),v);
}
int rnk(int x){
    int u,v;
    split(root,x - 1,u,v);
    int ret = t[u].siz + 1;
    root = merge(u,v);
    return ret;
}
int kth(int u,int x){
    int tmp = t[t[u].lc].siz + 1;
    if(x == tmp)
        return t[u].val;
    if(x < tmp)
        return kth(t[u].lc,x);
    else
        return kth(t[u].rc,x - tmp);
}
int pre(int x){
    int u,v;
    split(root,x - 1,u,v);
    int ret = kth(u,t[u].siz);
    root = merge(u,v);
    return ret;
}
int nex(int x){
    int u,v;
    split(root,x,u,v);
    int ret = kth(v,1);
    root = merge(u,v);
    return ret;
}

int main(){
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int q;
    cin >> q;
    while(q--){
        int op,x;
        cin >> op >> x;
        if(op == 1)
            insert(x);
        if(op == 2)
            remove(x);
        if(op == 3)
            cout << rnk(x) << '\n';
        if(op == 4)
            cout << kth(root,x) << '\n';
        if(op == 5)
            cout << pre(x) << '\n';
        if(op == 6)
            cout << nex(x) << '\n';
    }
    return 0;
}

例题 1：LOG

这里只讲平衡树的应用，略过了查询的分析过程。

经过分析（参考第一篇题解），本题回答能当且仅当：

所有数的和减大于 s 的数的和加上“大于 s 的数的个数乘 s”。

这个问题非常好用 FHQ-Treap 解决。将原树分裂为两棵子树满足右子树包含所有大于 s 的数，就能查询大于 s 的数的和以及大于 s 的数的个数了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 9;
int n,q;
int a[N];
struct node{
    int val,sum,pri;
    int lc,rc;
    int siz;
} t[N];
int node_cnt,root;

void push_up(int u){
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
    t[u].sum = t[t[u].lc].sum + t[t[u].rc].sum + t[u].val;
}

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所有节点权值 <= x，右子树所有节点权值 > x
    if(u == 0){
        L = R = 0;
        return;
    }
    if(t[u].val <= x){
        L = u;
        split(t[u].rc,x,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

void new_node(int x){
    t[++node_cnt] = (node){x,x,rand() * rand(),0,0,1};
}
void insert(int x){
    int u,v;
    split(root,x,u,v);
    new_node(x);
    int tmp = merge(u,node_cnt);
    root = merge(tmp,v);
}
void remove(int x){
    int u,v,w;
    split(root,x,u,v);//分裂成 <= x 的子树和 > x 的子树 
    split(u,x - 1,u,w);//分裂成 < x 的子树和 == x 的子树 
    w = merge(t[w].lc,t[w].rc);//合并 w（== x 的子树） 的左右子树 ，相当于删除了一个 x
    root = merge(merge(u,w),v);
}
int rnk(int x){
    int u,v;
    split(root,x - 1,u,v);
    int ret = t[u].siz + 1;
    merge(u,v);
    return ret;
}
int kth(int u,int x){
    int tmp = t[t[u].lc].siz + 1;
    if(x == tmp)
        return u;
    if(x < tmp)
        return kth(t[u].lc,x);
    else
        return kth(t[u].rc,x - tmp);
}
int query1(int x){//查询大于x的数的个数 
    int u,v;
    split(root,x,u,v);
    int ret = t[v].siz;
    root = merge(u,v);
    return ret;
}
int query2(int x){//查询大于x的数的和 
    int u,v;
    split(root,x,u,v);
    int ret = t[v].sum;
    root = merge(u,v);
    return ret;
}

signed main(){
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    while(q--){
        string op;
        cin >> op;
        if(op == "U"){
            int k,v;
            cin >> k >> v;
            remove(a[k]);
            a[k] = v;
            insert(a[k]);
        }
        else if(op == "Z"){
            int c,s;
            cin >> c >> s;
            int tmp = t[root].sum - query2(s) + query1(s) * s;
            cout << (tmp >= c * s ? "TAK" : "NIE") << '\n';
        }
    }
    return 0;
}

【2】FHQ-Treap 维护序列

FHQ-Treap 和 Splay 一样，也是能维护序列的平衡树。

为什么平衡树能维护序列？这是因为两个等价的平衡树中序遍历是一样的，所以如果 BST 的关键字是下标的话，不管其怎么变，对应的序列都是一样的。

对于任何一个区间操作（假设为 [l,r]），可以把整棵 FHQ-Treap 分裂成 [1,l - 1]，[l,r]，[r + 1,n] 对应的三棵 FHQ-Treap。

不过不用像维护集合一样把下标存下来，比如在一个序列任意位置插入数时，分裂完后只要按照下标从小到大合并就没有问题（一个节点的下标肯定满足 FHQ-Treap 的性质）。

那么不把下标存起来，怎么分裂呢？

这就要用到一个序列下标是连续的这个性质了，因此，我们可以修改 split，把它改成把一棵 FHQ-Treap 前 x 个元素分裂出来。这就是所谓的“按排名分裂”。

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成两棵子树满足左子树的大小为x
    if(u == 0){
        L = R = 0;
        return;
    }
    push_down(u);
    if(t[t[u].lc].siz < x){
        L = u;
        split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}

FHQ-Treap 支持的操作很多样，接下来一个一个地看。

例题 1：文艺平衡树

区间翻转是一个基础的应用。方法如下：

将需要翻转的区间分裂出来
因为中序遍历代表整个序列，所以区间翻转相当于该子树所有节点都要交换左右子节点。这是极为低效的，考虑用懒标记优化。
最后把分裂出来的区间合并回去。

最后输出整个树的中序遍历。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n,m;
struct node{
    int val,pri;
    int lc,rc;
    int siz;
    int tag;
} t[N];
int node_cnt,root;

void push_up(int u){
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}

void make_tag(int u){
    t[u].tag ^= 1;
    swap(t[u].lc,t[u].rc);
} 
void push_down(int u){
    if(t[u].tag){
        make_tag(t[u].lc);
        make_tag(t[u].rc);
        t[u].tag = 0;
    }
}

//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x
void split(int u,int x,int &L,int &R){
    if(u == 0){
        L = R = 0;
        return;
    }
    push_down(u);
    if(t[t[u].lc].siz < x){
        L = u;
        split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根 
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    push_down(u);
    push_down(v);
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

void new_node(int x){
    t[++node_cnt] = (node){x,rand() * rand(),0,0,1,0};
}

void reverse(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    make_tag(v);
    root = merge(merge(u,v),w);
}

void print(int u){
    if(!u)
        return;
    push_down(u);
    print(t[u].lc);
    cout << u << ' ';
    print(t[u].rc);
}

int main(){
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        new_node(i);
        root = merge(root,node_cnt);
    }
    while(m--){
        int l,r;
        cin >> l >> r;
        reverse(l,r);
    }
    print(root);
    return 0;
}

例题 2：文本编辑器

区间插入多个元素的话有两种实现方法：

一个一个元素插入，这在本题中可以通过，但不够高效。
把需要插入元素的 FHQ-Treap 以线性时间复杂度建出来，将原树从光标位置分裂开，依次合并左子树、新树和右子树。

区间删除就是把需要删除的区间分裂出来，然后直接合并两个不需要删除的区间。

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 4e6 + 9;
int n,m;
char a[N]; 
struct node{
    char val;
    int pri;
    int lc,rc;
    int siz;
} t[N];
int node_cnt,root;

void push_up(int u){
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
}

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x，
    if(u == 0){
        L = R = 0;
        return;
    }
    if(t[t[u].lc].siz < x){
        L = u;
        split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根 
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

int new_node(char x){
    t[++node_cnt] = (node){
                        x,
                        rand() * rand(),
                        0,0,
                        1,
    };
    return node_cnt;
}

int build(int l,int r){
    if(l == r)
        return new_node(a[l]);
    int u = merge(build(l,mid),build(mid + 1,r));
    return u;
}

void Insert(int pos,int len){
    int u,v;
    split(root,pos,u,v);
    int top = 0;
    for(int i = 1;i <= len;i++){
        char c = getchar();
        while(c < 32 || c > 126)
            c = getchar();
        a[++top] = c;
    }
    root = merge(merge(u,build(1,top)),v);
}
void Delete(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    root = merge(u,w);
}

void Print(int u){
    if(!u)
        return;
    Print(t[u].lc);
    cout << t[u].val;
    Print(t[u].rc);
}

void print(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    Print(v);
    cout << '\n';
    root = merge(merge(u,v),w);
}

signed main(){
    srand(time(0));
    cin >> m;
    int pos = 0;
    while(m--){
        string op;
        int len;
        cin >> op;
        if(op == "Move")
            cin >> pos;
        else if(op == "Insert"){
            cin >> len;
            Insert(pos,len);
        }
        else if(op == "Delete"){
            cin >> len;
            Delete(pos + 1,pos + len);
        }
        else if(op == "Get"){
            cin >> len;
            print(pos + 1,pos + len);
        }
        else if(op == "Prev")
            pos--;
        else if(op == "Next")
            pos++;
    }
    return 0;
}

例题 3：维护序列

本题中还要维护区间信息/区间推平，实现方法和线段树一样，但是在 push_up 的时候不要漏了当前节点的值！这个和线段树不一样！！！

#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 4e6 + 9,INF = 0x3f3f3f;
int n,m;
int a[N]; 
struct node{
    int val;
    int sum,Max,lsum,rsum;
    int pri;
    int lc,rc;
    int siz;
    int rev_tag,mod_tag;
} t[N];
int node_cnt,root;

void push_up(int u){
    t[u].siz = t[t[u].lc].siz + t[t[u].rc].siz + 1;
    t[u].sum = t[t[u].lc].sum + t[t[u].rc].sum + t[u].val;//不要漏了t[u].val！！！ 
    t[u].Max = max(t[u].val + t[t[u].lc].rsum + t[t[u].rc].lsum,t[u].val);
    if(t[u].lc)
        t[u].Max = max(t[u].Max,t[t[u].lc].Max);
    if(t[u].rc)
        t[u].Max = max(t[u].Max,t[t[u].rc].Max);
    //不要漏了t[u].val！！！ 
    t[u].lsum = max(max(t[t[u].lc].lsum,t[t[u].lc].sum + t[u].val + t[t[u].rc].lsum),0);
    t[u].rsum = max(max(t[t[u].rc].rsum,t[t[u].rc].sum + t[u].val + t[t[u].lc].rsum),0);
}
void make_rev_tag(int u){
    t[u].rev_tag ^= 1;
    swap(t[u].lc,t[u].rc);
    swap(t[u].lsum,t[u].rsum);
}
void make_mod_tag(int u,int v){
    t[u].val = t[u].mod_tag = v;
    t[u].sum = v * t[u].siz;
    t[u].Max = max(v,t[u].sum);
    t[u].lsum = t[u].rsum = max(t[u].sum,0);
} 
void push_down(int u){
    if(t[u].rev_tag){
        make_rev_tag(t[u].lc);
        make_rev_tag(t[u].rc);
        t[u].rev_tag = 0;
    }
    if(t[u].mod_tag != -INF){
        make_mod_tag(t[u].lc,t[u].mod_tag);
        make_mod_tag(t[u].rc,t[u].mod_tag);
        t[u].mod_tag = -INF;
    }
}

void split(int u,int x,int &L,int &R){//将以u为根的子树分裂成以L,R为根的两棵子树满足左子树所大小为x，
    if(u == 0){
        L = R = 0;
        return;
    }
    push_down(u);
    if(t[t[u].lc].siz < x){
        L = u;
        split(t[u].rc,x - t[t[u].lc].siz - 1,t[u].rc,R);
    }
    else{
        R = u;
        split(t[u].lc,x,L,t[u].lc);
    }
    push_up(u);
}
int merge(int u,int v){//将以u为根的树和以v为根的子树合并并返回合并后的根 
    if(!u || !v)//如果其中一个根为空那么合并后的根就是另一个根 
        return u | v;
    push_down(u);
    push_down(v);
    if(t[u].pri > t[v].pri){//u优先级大于v优先级，则u应为v的父亲（大根堆性质） 
        t[u].rc = merge(t[u].rc,v);//t[t[u].lc].val <= t[u].val <= t[v].val，所以合并t[u].rc和v
        push_up(u);
        return u;
    }
    else{//否则v应为u的父亲 
        t[v].lc = merge(u,t[v].lc);//t[t[v].rc].val >= t[v].val >= t[u].val，所以合并u和t[v].lc 
        push_up(v);
        return v;
    }
}

int new_node(int x){
    t[++node_cnt] = (node){
                        x,
                        x,x,max(x,0),max(x,0),
                        rand() * rand(),
                        0,0,
                        1,
                        0,-INF
    };
    return node_cnt;
}

int build(int l,int r){
    if(l == r)
        return new_node(a[l]);
    int u = merge(build(l,mid),build(mid + 1,r));
    //push_up(u);
    return u;
}

void Insert(int pos,int tot){
    int u,v;
    split(root,pos,u,v);
    for(int i = 1;i <= tot;i++)
        cin >> a[i];
    root = merge(merge(u,build(1,tot)),v);
}
void Delete(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    root = merge(u,w);
}
void Modify(int l,int r,int k){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    make_mod_tag(v,k);
    root = merge(merge(u,v),w);
}
void Reverse(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    make_rev_tag(v);
    root = merge(merge(u,v),w);
}

int query_sum(int l,int r){
    int u,v,w;
    split(root,r,u,w);
    split(u,l - 1,u,v);
    int ret = t[v].sum;
    root = merge(merge(u,v),w);
    return ret;
}

signed main(){
    srand(time(0));
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    root = merge(root,build(1,n));
    while(m--){
        string op;
        int pos,tot;
        cin >> op;
        if(op == "INSERT"){
            cin >> pos >> tot;
            Insert(pos,tot);
        }
        else if(op == "DELETE"){
            cin >> pos >> tot;
            Delete(pos,pos + tot - 1);
        }
        else if(op == "MAKE-SAME"){
            int v;
            cin >> pos >> tot >> v;
            Modify(pos,pos + tot - 1,v);
        }
        else if(op == "REVERSE"){
            cin >> pos >> tot;
            Reverse(pos,pos + tot - 1);
        }
        else if(op == "GET-SUM"){
            cin >> pos >> tot;
            cout << query_sum(pos,pos + tot - 1) << '\n';
        }
        else if(op == "MAX-SUM")
            cout << t[root].Max << '\n';
    }
    return 0;
}

例题 4：SuperMemo

其实和上面一题没什么区别，REVOLVE 操作也不难实现。见题解。