POJ-3468 A Simple Problem with Integers ( 线段树 )

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

4
55
9
15

询问区间和并对区间进行操作。
对区间操作是不能点更新，应该区间更新，不然会超时 例如区间(1,10)，我要对(3,8)进行操作，点更新需要进行(1,5),(1,3),(3,3),(4,5),(4,4),(5,5),(6,10),(6,8),(6,7),(6,6),(7,7),(8,8)共12步，而区间操作只需要(1,5),(1,3),(3,3),(4,5),(6,10),(6,8)共6步，而这只是一种简单的情况。
进行区间操作需要在节点加入一个参数add，用来记录该区间每个元素的增值以避免点更新。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 class node{
 6 public:
 7     int l, r;
 8     long long v, add; //v为该区间的和，并用add记录加在该区间上的值
 9     node *left, *right;
10 };
11 long long num[100005];
12 
13 node *Creat( int z, int y ){
14     node *root = new node;
15     root->l = z;
16     root->r = y;
17     root->add = 0;
18     root->left = NULL;
19     root->right = NULL;
20     if( z == y ){
21         root->v = num[z];
22         return root;
23     }
24 
25     int mid = ( z + y ) >> 1;
26     root->left = Creat( z, mid );
27     root->right = Creat( mid + 1, y );
28 
29     root->v = root->left->v + root->right->v;
30 
31     return root;
32 }
33 
34 void Insert( int z, int y, long long n, node *p ){
35     if( z == p->l && y == p->r ){
36         p->add += n;
37         return;
38     }
39 
40     p->v += ( y - z + 1 ) * n;
41 
42     int mid = ( p->l + p->r ) >> 1;
43 
44     if( y <= mid ) Insert( z, y, n, p->left );
45     else if( z > mid ) Insert( z, y, n, p->right );
46     else{
47         Insert( z, mid, n, p->left );
48         Insert( mid +1, y, n, p->right );
49     }
50 }
51 
52 long long Ask( int z, int y,node *p ){
53     long long ans = 0;
54 
55     if( z == p->l && y == p->r )
56         return p->v + p->add * ( y - z +1 );
57 
58     ans += p->add * ( y - z + 1 );
59     
60     int mid = ( p->l + p->r ) >> 1;
61 
62     if( y <= mid ) ans += Ask( z, y, p->left );
63     else if( z > mid ) ans += Ask( z, y, p->right );
64     else
65         ans += Ask( z, mid, p->left ) + Ask( mid + 1, y, p->right );
66     
67     return ans;
68 }
69 
70 int main(){
71     ios::sync_with_stdio( false );
72 
73     int N, Q;
74     cin >> N >> Q;
75 
76     for( int i = 1; i <= N; i++ )
77         cin >> num[i];
78 
79     node *root = Creat( 1, N );
80 
81     int a, b;
82     long long c;
83     char k;
84     for( int i = 1; i <= Q; i++ ){
85         cin >> k;
86         
87         if( k == 'C' ){
88             cin >> a >> b >> c;
89             Insert( a, b, c, root);
90         }
91 
92         else{
93             cin >> a >> b;
94             cout << Ask( a, b, root ) << endl;
95         }
96     }
97 
98     return 0;
99 }

POJ-3468 A Simple Problem with Integers ( 线段树 )

相关推荐