Algorithm

splay

splay 是一种很灵活的数据结构。它是动态树的基础，动态树是维护树上数据的神器啊~

splay是一种特殊的二叉查找树，与平衡树不同，不是按照判断高度来降低深度的。
每次插入一个点，或者每次处理一个点，都需要进行一次splay操作把该点移动到根，根据数据的局部性原理，可以使处理变得快一点。

###它有以下规则：（p是x的parent节点）
zig

  • 当p为根节点时，进行zip step操作。
  • 当x是p的左孩子时，对x右旋；
  • 当x是p的右孩子时，对x左旋。

zig-zig

  • 当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。
  • 当p为左孩子，x为右孩子时，将x左旋后再右旋。
  • 当p为右孩子，x为左孩子时，将x右旋后再左旋。

zig-zag

  • 当p不是根节点，且x和p不同为左孩子或右孩子时，进行Zig-Zag操作。
  • 当p为左孩子，x为右孩子时，将x左旋后再右旋。
  • 当p为右孩子，x为左孩子时，将x右旋后再左旋。

splay可以替代线段树进行更加复杂的区间操作，但是一般如果不是线段树解决不了的问题，尽量不能用splay做，因为splay常数比线段树大很多。

splay的维护懒惰标记也很巧妙，每次旋转的时候先把标记下降，然后旋转，旋转之后只有该节点原来的父亲的数据会发生变化，需要pushup一下，当前节点的数据可以等位置固定了之后再维护。

如果要计算一段区间内的值，可以先把该段位置的前一个节点splay到根，然后把该段位置的后一个节点splay到root,这样的话，后一个的节点的左子树就是该段区间所维护的值了。

下面是一个实现：

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/***********************************************\
 |Author: YMC
 |Created Time: 2015/3/25 21:34:19
 |File Name: hdu1166.cpp
 |Description: 
\***********************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)
#define mset(l,n) memset(l,n,sizeof(l))
#define rep(i,n) for(int i=0;i<n;++i)
#define maxx(a) memset(a, 0x3f, sizeof(a))
#define zero(a) memset(a, 0, sizeof(a))
#define srep(i,n) for(int i = 1;i <= n;i ++)
#define MP make_pair
const int inf=0x3f3f3f3f ;
const double eps=1e-8 ;
const double pi=acos (-1.0);
typedef long long ll;
using namespace std;
#define maxn 110000
struct Node {
    int val;
    int sum;
    int add;
    Node* ch[2], *f;
    int size;
    void init() {
        f = ch[0] = ch[1] = NULL; size = 1;
        add = 0;    //延迟标记
    }
    void rot(int c) {
        Node *y = f, *z = y->f;
        //y->push_down(); push_down();
        y->ch[!c] = ch[c];  if(ch[c]) ch[c]->f = y;
        f = z;
        if(z) {
            if(y == z->ch[0])   z->ch[0] = this;
            else z->ch[1] = this;
        }
        ch[c] = y;  y->f = this;
        y->update();    //自己暂时不更新,y是原来的fa,在自己下面
    }
    void splay(Node *fa) {
        for(pushdown(); f != fa; ) {    //每次自己要旋转,则需要把标记传递下去,子标记不受影响。
            if(f->f == fa) {
                if(f->ch[0] == this) rot(1);
                else rot(0);
            } else {
                Node *y = f, *z = y->f;
                if(y->ch[0] == this) {
                    if(z->ch[0] == y) {
                        y->rot(1); rot(1);
                    } else {
                        rot(1); rot(0);
                    }
                } else {
                    if(z->ch[0] != y) {
                        y->rot(0); rot(0);
                    } else {
                        rot(0); rot(1);
                    }
                }
            }
        }
        update();   //本节点最后更新
    }
    void pushdown() {
        if(add) {
            if(ch[0]) {
                ch[0]->add += add;
                ch[0]->val += add;
                ch[0]->sum += ch[0]->size * add;
            }
            if(ch[1]) {
                ch[1]->add += add;
                ch[1]->val += add;
                ch[1]->sum += ch[1]->size * add;
            }
            add = 0;
        }
    }
    void update() {
        size = 1;
        if(ch[0]) size += ch[0]->size;
        if(ch[1]) size += ch[1]->size;
        sum = val;
        if(ch[0]) sum += ch[0]->sum;
        if(ch[1]) sum += ch[1]->sum;
    }
    Node* find(int r) {
        pushdown();     //找的时候要维护一些信息。不然找到的节点的信息错误
        int L = 0; if(ch[0]) L += ch[0]->size;
        if(r <= L) return ch[0]->find(r);
        if(r == L+1) return this;
        return ch[1]->find(r-L-1);
    }
}node[maxn];
int e;
inline Node* _alloc() {
    node[e].init(); return &node[e++];
}
int da[maxn];
Node* _make(int l, int r) {
    if(l > r) return NULL;
    int mid = l + r >> 1;   //从中间开始建，树的深度最小
    Node *p = _alloc(); p->val = da[mid];
    p->ch[0] = _make(l, mid-1); if(p->ch[0]) p->ch[0]->f = p;
    p->ch[1] = _make(mid+1, r); if(p->ch[1]) p->ch[1]->f = p;
    p->update();    //子节点更新好之后再更新自己。
    return p;
}
char op[10];
int a, b, c, n;
int main() {
	//freopen("input.txt","r",stdin); 
    int T;
    scanf("%d",&T);
    int cas = 0;
    while(T--) {
        printf("Case %d:\n", ++cas);
        scanf("%d",&n);
        srep(i,n) scanf("%d",&da[i]);
        da[0] = da[n+1] = 0;
        e = 0;
        Node *root = _make(0, n+1), *tp;
        while(scanf("%s",op) != EOF) {
            if(op[0] == 'Q') {
                scanf("%d %d",&a,&b); a++; b++;
                tp = root->find(a - 1);
                tp->splay(NULL); root = tp;
                tp = root->find(b + 1);
                tp->splay(root);
                tp = tp->ch[0];
                printf("%d\n",tp->sum);
            } else if(op[0] == 'A') {
                scanf("%d %d",&a,&b); a++;
                tp = root->find(a-1);
                tp->splay(NULL);    root = tp;
                tp = root->find(a+1);
                tp->splay(root);
                tp = tp->ch[0];
                tp->sum += b;
            } else if(op[0] == 'S') {
                scanf("%d %d",&a,&b); a++;
                tp = root->find(a-1);
                tp->splay(NULL);    root = tp;
                tp = root->find(a+1);
                tp->splay(root);
                tp = tp->ch[0];
                tp->sum -= b;
            } else break;
        }
    }
	return 0;
}