引言
Splay Tree（伸展树）是一种高效的自调整二叉搜索树，能够支持多种区间操作。本文将详细介绍如何利用Splay Tree实现插入、删除、修改、翻转和求和等操作。
1. 插入操作
与普通题目不同，这里的插入是插入一段连续的数据。如果逐个插入会非常耗时，因此我们先将要插入的一段数据构建成一个平衡树，然后整体插入到目标位置。
2. 删除操作
删除操作需要删除一个区间 [L, R]。具体步骤如下：将 L-1 旋转到根节点，将 R+1 旋转到根节点的右子节点，此时 [L, R] 就位于根节点的右子节点的左子树中，直接删除即可。需要注意的是，删除后的节点可以回收再利用以节省空间。
3. 修改操作
对于区间修改，可以在节点上打标记，以便在后续操作中更新。这样可以减少不必要的重复计算。
4. 翻转操作
翻转操作同样可以通过打标记来实现，且与修改操作的标记互不影响。具体的实现方式可参考文艺平衡树。
5. 求和操作
类似于线段树的求和操作，每个节点维护一个 sum 值。通过递归更新父节点的 sum 值，可以高效地计算区间和。
6. 求和最大的子列
每个节点需要维护三个信息：最大前缀和 lx，最大后缀和 rx，以及最大子列和 maxx。在 pushup 操作时，根据左右子树的信息更新当前节点的这三个值。
#include
#define INF 2100000001
#define N 500003
#define M 4000003
#define LL long long
using namespace std;
int root, ndnum = 0;
char s[12];
int a[N];
int ch[N][3], rev[N], tag[N], siz[N], f[N], key[N];
LL sum[N], lx[N], rx[N], maxx[N];
queue
int get(int x) { return ch[f[x]][1] == x; }
void update(int x) { if (!x) return; int l = ch[x][0], r = ch[x][1]; siz[x] = siz[l] + siz[r] + 1; sum[x] = sum[l] + sum[r] + key[x]; lx[x] = max(lx[l], sum[l] + key[x] + max((LL)0, lx[r])); rx[x] = max(rx[r], sum[r] + key[x] + max((LL)0, rx[l])); maxx[x] = max(max(rx[l], (LL)0) + key[x] + max(lx[r], (LL)0), max(maxx[l], maxx[r])); }
int build(int fa, int l, int r) { if (l > r) return 0; int mid = (l + r) >> 1, now; if (q.empty()) now = ++ndnum; else { now = q.front(); q.pop(); } key[now] = a[mid]; f[now] = fa; tag[now] = -INF; sum[now] = 0; siz[now] = 1; rev[now] = 0; ch[now][0] = build(now, l, mid - 1); ch[now][1] = build(now, mid + 1, r); update(now); return now; }
void modify(int k, int c) { if (!k) return; tag[k] = key[k] = c; sum[k] = siz[k] * c; maxx[k] = rx[k] = lx[k] = max(sum[k], (LL)c); }
void turn(int k) { if (!k) return; rev[k] ^= 1; swap(ch[k][0], ch[k][1]); swap(lx[k], rx[k]); }
void pushdown(int k) { if (!k) return; if (tag[k] != -INF) { modify(ch[k][0], tag[k]); modify(ch[k][1], tag[k]); tag[k] = -INF; } if (rev[k]) { turn(ch[k][0]); turn(ch[k][1]); rev[k] = 0; } }
void rotate(int x) { int old = f[x]; int oldf = f[old]; int which = get(x); ch[old][which] = ch[x][which ^ 1]; f[ch[old][which]] = old; ch[x][which ^ 1] = old; f[old] = x; f[x] = oldf; if (oldf) ch[oldf][ch[oldf][1] == old] = x; update(old); update(x); }
void splay(int x, int tar) { for (int fa; (fa = f[x]) != tar; rotate(x)) if (f[fa] != tar) rotate((get(fa) == get(x)) ? fa : x); if (!tar) root = x; pushdown(root); }
void qing(int &x) { if (!x) return; f[x] = 0; qing(ch[x][0]); qing(ch[x][1]); lx[x] = rx[x] = maxx[x] = -INF; siz[x] = 0; tag[x] = -INF; rev[x] = 0; sum[x] = 0; q.push(x); ch[x][0] = ch[x][1] = 0; x = 0; }
int find(int x) { int now = root; while (1) { pushdown(now); if (x <= siz[ch[now][0]]) now = ch[now][0]; else { x -= siz[ch[now][0]] + 1; if (!x) return now; now = ch[now][1]; } } }
LL query_sum(int k) { return sum[k]; }
int main() { int n = read(), m = read(); for (int i = 1; i <= n; ++i) a[i + 1] = read(); a[1] = -INF; a[n + 2] = -INF; rx[0] = lx[0] = maxx[0] = -INF; root = build(0, 1, n + 2); for (int i = 1; i <= m; ++i) { scanf("%s", s); if (s[0] == 'I') { memset(a, 0, sizeof(a)); int pos = read(), tot = read(); for (int j = 1; j <= tot; ++j) a[j] = read(); int tmp = build(-1, 1, tot); int x = find(pos + 1), y = find(pos + 2); splay(x, 0); splay(y, x); f[tmp] = y; ch[y][0] = tmp; update(y); update(x); } if (s[0] == 'D') { int pos = read(), tot = read(); int x = find(pos), y = find(pos + tot + 1); splay(x, 0); splay(y, x); qing(ch[y][0]); update(y); update(x); } if (s[0] == 'M' && s[2] == 'K') { int pos = read(), tot = read(), c = read(); int x = find(pos), y = find(pos + tot + 1); splay(x, 0); splay(y, x); modify(ch[y][0], c); update(y); update(x); } if (s[0] == 'R') { int pos = read(), tot = read(); int x = find(pos), y = find(pos + tot + 1); splay(x, 0); splay(y, x); turn(ch[y][0]); update(y); update(x); } if (s[0] == 'G') { int pos = read(), tot = read(); int x = find(pos), y = find(pos + tot + 1); splay(x, 0); splay(y, x); update(y); update(x); printf("%lld
", sum[ch[y][0]]); } if (s[0] == 'M' && s[2] == 'X') { printf("%lld
", maxx[root]); } } }
特别需要注意的是哨兵节点的设置。为了不影响最终答案，我们将前后哨兵节点的值设为 -INF。最后输出最大子列和时，只需输出 root 的 maxx 即可。
京公网安备 11010802041100号