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

· · 算法·理论

请保证你有 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 的两个基本操作:splitmerge

无论是维护集合还是维护序列,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 操作要求左子树的最大值小于右子树的最小值。在此基础上,我们要保证随机权值满足堆的性质。

设需要合并的两棵子树的根为 uv,如果 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

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

经过分析(参考第一篇题解),本题回答能当且仅当:

这个问题非常好用 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:文本编辑器

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

  1. 一个一个元素插入,这在本题中可以通过,但不够高效。

  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 操作也不难实现。见题解。