利用伸展树高效处理区间操作

### 利用伸展树高效处理区间操作

考虑一个从1开始编号的序列，记作A[1...N]，我们可以在其上执行多种区间操作。例如，将区间[s, e]中的所有元素增加一个值delta，查询区间[s, e]中所有元素的和或极值，甚至将区间[s, e]从原序列中删除，并将新的元素插入到指定位置。

为了高效处理这些操作，我们可以构建一棵伸展树，其中每个节点的键值为原序列的下标。这棵树的中序遍历结果即为原序列。由于伸展操作不会改变键值的顺序，因此这棵树始终与原序列一一对应，从而可以将对序列的操作转换为对伸展树的操作。

在伸展树上进行区间操作非常直观。具体来说，将s-1伸展至树根，将e+1伸展为根的右子节点，则根的右子节点的左子节点就代表了区间[s, e]。为了确保s-1和e+1的存在，可以将原序列扩展为A[0...N+1]。通过在节点上添加相应的附加信息，可以轻松解决各种区间问题。

#### size域在伸展树中的重要应用

如果在节点中直接存储下标作为键值，那么在进行区间删除操作时，某些节点的键值需要更新，这会导致O(N)的时间复杂度，超出预期的O(log N)。因此，对于需要改变序列结构的区间操作，更好的方法是不显式存储键值。

节点的键值实际上是其在序列中的相对位置，可以通过size域来隐式表示。size域记录了以该节点为根的子树中节点的数量，可以用于解决第k小的问题。例如，s-1实际上是第s-1小的下标，e+1则是第e+1小的下标。

维护size域非常简单。在进行区间删除操作时，只需更新涉及的两个节点的size域，这是一个常数时间操作。通过这种方式，伸展树可以高效地处理区间删除、区间增加、区间翻转等操作，同时仍能完成区间和、区间极值的查询以及成段修改序列元素等任务。

#### 示例代码：使用伸展树解决hdu1754

```cpp
#include
#include

int const SIZE = 200003;
int const LEFT = 0;
int const RIGHT = 1;
typedef int value_t;

struct node_t {
int parent;
int child[2];
int sn;
int size;
value_t value;
value_t peak;
} Node[SIZE];

int toUsed = 0;
int Root = 0;

inline void init() {
toUsed = Root = 0;
memset(Node, 0, sizeof(node_t));
}

inline void _pushUp(int t) {
Node[t].size = 1;
Node[t].peak = Node[t].value;
int son = Node[t].child[LEFT];
if (son) {
Node[t].size += Node[son].size;
if (Node[t].peak }
son = Node[t].child[RIGHT];
if (son) {
Node[t].size += Node[son].size;
if (Node[t].peak }
}

inline int _newNode() {
++toUsed;
memset(Node + toUsed, 0, sizeof(node_t));
return toUsed;
}

inline void _link(int p, int sn, int t) {
Node[p].child[sn] = t;
Node[t].parent = p;
Node[t].sn = sn;
}

inline void _rotate(int t) {
int p = Node[t].parent;
int sn = Node[t].sn;
int osn = sn ^ 1;
_link(p, sn, Node[t].child[osn]);
_link(Node[p].parent, Node[p].sn, t);
_link(t, osn, p);
_pushUp(p);
}

void _splay(int t, int p, int &root) {
while (Node[t].parent != p) {
int pp = Node[t].parent;
if (Node[pp].parent != p) Node[pp].sn == Node[t].sn ? _rotate(pp) : _rotate(t);
_rotate(t);
}
_pushUp(t);
if (0 == p) root = t;
}

int _kth(int root, int index) {
int son = Node[root].child[LEFT];
int ss = son ? Node[son].size : 0;
if (ss == index) return root;
return index }

void build(int &t, int parent, int sn, int s, int e, value_t const a[]) {
int mid = (s + e) >> 1;
t = _newNode();
Node[t].parent = parent;
Node[t].value = a[mid];
Node[t].sn = sn;
if (mid > s) build(Node[t].child[LEFT], t, LEFT, s, mid - 1, a);
if (mid _pushUp(t);
}

int query(int &root, int s, int e) {
int t = _kth(root, s - 1);
_splay(t, 0, root);
t = _kth(root, e + 1);
_splay(t, root, root);
return Node[Node[t].child[LEFT]].peak;
}

void modify(int &root, int idx, value_t v) {
int t = _kth(root, idx);
_splay(t, 0, root);
Node[t].value = v;
if (Node[t].peak }

int N, M;
int A[SIZE] = {0};

bool read() {
if (EOF == scanf("%d%d", &N, &M)) return false;
for (int i = 1; i <= N; ++i) scanf("%d", A + i);
A[N + 1] = 0;
return true;
}

int main() {
while (read()) {
init();
build(Root, 0, 0, 0, N + 1, A);
while (M--) {
char cmd[3];
int a, b;
scanf("%s%d%d", cmd, &a, &b);
if ('Q' == *cmd) {
printf("%d\n", query(Root, a, b));
} else {
modify(Root, a, b);
}
}
}
return 0;
}
```

通过上述方法，伸展树不仅能够高效处理静态区间问题，还能灵活应对动态变化的序列结构。