【POJ3468】【树状数组区间修改】A Simple Problem with Integers

时间：2023-03-09 13:33:48
【POJ3468】【树状数组区间修改】A Simple Problem with Integers

Description

You have N integers, A1, A2, ... , AN. 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 A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

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

Hint

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

Source

【分析】

以前一直以为树状数组只能单点修改，区间询问，今天算是见识到了树状数组的区间修改了。

不说多的了，很巧妙的感觉，对于一个修改操作(a,b,c)，将[a,b]区间整体加上一个c

可以把它拆开成两个部分(a,n,c),和(b + 1,n,-c)，这个时候就好做了，用两个树状数组。

一个树状数组记录从修改点开始一直到结束所增加的所有量，及c*(n-a+1)。另一个记录下增量值c。

那么对于一个在a点右边而在b点左边的点x,它所得到的增量为c*(n-a+1) - c*(n-x)。很好维护了。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <utility>

 #include <iomanip>

 #include <string>

 #include <cmath>

 #include <map>

 const int MAXN =  + ;

 const int MAX =  + ;

 using namespace std;

 typedef long long ll;

 int n, m;

 ll sum[MAXN];//记录原始序列

 ll C[][MAXN]; 

 int lowbit(int x){return x&-x;}

 ll get(int k, int x){

     ll cnt = ;

     while (x > ){

           cnt += C[k][x];

           x -= lowbit(x);

     }

     return cnt;

 }

 void add(int k, int x, ll val){

      while (x <= n){

            C[k][x] += val;

            x += lowbit(x);

      }

      return ;

 }

 void work(){

      memset(C, , sizeof(C));//0记录总值、1录增量

      sum[] = ;

      scanf("%d%d", &n, &m);

      for (int i = ; i <= n; i++){

          scanf("%lld", &sum[i]);

          sum[i] += sum[i - ];

      }

      for (int i = ; i <= m; i++){

          char str[];

          scanf("%s", str);

          if (str[] == 'Q'){

             int l, r;

             scanf("%d%d", &l, &r);

             printf("%lld\n", sum[r] - sum[l - ] +(get(, r) - get(, r) * (n - r)) - (get(, l - ) - get(, l - ) * (n - l + )));

          }else{

                int l, r;

                ll x;

                scanf("%d%d%lld", &l, &r, &x);

                add(, l, (n - l + ) * x);

                add(, r + , (n - r) * (-x));

                add(, l, x);

                add(, r + , -x);

          }

      }

      //printf("\n%d\n", get(0, 10));

 }

 int main(){

     int T;

     #ifdef LOCAL

     freopen("data.txt",  "r",  stdin);

     freopen("out.txt",  "w",  stdout);

     #endif

     work();

     return ;

 }

相关文章