Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers

本文主要是介绍Splay树（区间更新）—— POJ 3468 A Simple Problem with Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对应POJ 题目：点击打开链接

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 72765		Accepted: 22465
Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

题意：

输入n，m；表示有n个数和m个询问。接着输入每个数的初始值。接着每个询问表示：Q表示求解i,j区间的和，C表示i~j区间的每个值都+k

思路：

Splay树区间更新问题，注意在更新标记后向上更新。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))typedef struct TREE
{long long sum; //以该结点为根的树的元素和TREE *fa, *l, *r;int sz; //以该结点为根的树的总结点数int add; //懒惰标记
}Tree;void Push_down(Tree *T)
{if(NULL == T) return;if(T->add){T->sum += ((long long)(T->sz) * T->add);if(T->l) T->l->add += T->add;if(T->r) T->r->add += T->add;T->add = 0;}
}void Init(Tree *&T, int n)
{int i;long long a;Tree *cur, *pre;pre = (Tree *)malloc(sizeof(Tree));pre->sum = 0;pre->fa = pre->l = pre->r = NULL;pre->sz = 1;pre->add = 0;for(i = n - 1; i > -1; i--){cur = (Tree *)malloc(sizeof(Tree));scanf("%I64d", &a);cur->l = pre;cur->r = NULL;pre->fa = cur;cur->sz = pre->sz + 1;cur->sum = a + pre->sum;cur->add = 0;pre = cur;if(0 == i){cur = (Tree *)malloc(sizeof(Tree));cur->fa = NULL;cur->l = pre;cur->r = NULL;pre->fa = cur;cur->sz = pre->sz + 1;cur->sum = pre->sum;cur->add = 0;}}T = cur;
}void R_rotate(Tree *x)
{Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->r;int sx = x->sz, sy = y->sz, sk = 0;long long sumx = x->sum, sumy = y->sum, sumk = 0;if(k){Push_down(k);sk = k->sz;sumk = k->sum;}y->l = k;x->r = y;if(z){if(y == z->l) z->l = x;else z->r = x;}if(k) k->fa = y;y->fa = x;x->fa = z;y->sz = sy - sx + sk;x->sz = sx - sk + y->sz;y->sum = sumy - sumx + sumk;x->sum = sumx - sumk + y->sum;
}void L_rotate(Tree *x)
{Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->l;int sx = x->sz, sy = y->sz, sk = 0;long long sumx = x->sum, sumy = y->sum, sumk = 0;if(k){Push_down(k);sk = k->sz;sumk = k->sum;}y->r = k;x->l = y;if(z){if(y == z->r) z->r = x;else z->l = x;}if(k) k->fa = y;y->fa = x;x->fa = z;y->sz = sy - sx + sk;x->sz = sx - sk + y->sz;y->sum = sumy - sumx + sumk;x->sum = sumx - sumk + y->sum;
}//寻找第x个数的结点
Tree *FindTag(Tree *T, int x)
{if(NULL == T) return NULL;Push_down(T);Tree *p;p = T;int sum = (p->l ? p->l->sz : 0) + 1;while(sum != x && p){if(sum < x){p = p->r;x -= sum;}else p = p->l;Push_down(p);sum = (p->l ? p->l->sz : 0) + 1;}return p;
}void Splay(int x, Tree *&T)
{Push_down(T);Tree *p, *X, *end, *new_t;end = T->fa;new_t = T;if(end) new_t = T->fa;X = FindTag(new_t, x);while(X->fa != end){p = X->fa;if(end == p->fa){ //p是根结点if(X == p->l) R_rotate(X);else L_rotate(X);break;}//p不是根结点if(X == p->l){if(p == p->fa->l){R_rotate(p); //LLR_rotate(X); //LL}else{R_rotate(X); //RLL_rotate(X);}}else{if(p == p->fa->r){ //RRL_rotate(p);L_rotate(X);}else{ //LRL_rotate(X);R_rotate(X);}}}T = X;
}void FreeTree(Tree *T)
{if(NULL == T) return;FreeTree(T->l);FreeTree(T->r);free(T);
}void InOrder(Tree *T)
{if(NULL == T) return;Push_down(T);InOrder(T->l);printf("%d ", T->sum);InOrder(T->r);
}int main()
{//freopen("in.txt", "r", stdin);Tree *T;T = NULL;int n, q;int a, b, c;char s[3];scanf("%d%d", &n, &q);Init(T, n);while(q--){//InOrder(T);//printf("\n");scanf("%s", s);if('Q' == s[0]){scanf("%d%d", &a, &b);a++; b++;Splay(a - 1, T);Splay(b + 1, T->r);Push_down(T->r->l);printf("%I64d\n", T->r->l->sum);}else{scanf("%d%d%d", &a, &b, &c);a++; b++;Splay(a - 1, T);Splay(b + 1, T->r);T->r->l->add += c;//向上更新T->r->sum += ((long long)(b - a + 1) * c);T->sum += ((long long)(b - a + 1) * c);}}FreeTree(T);return 0;
}