POJ: 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.

Problem Analysis:

If we add the number to the given internal one by one, then the time complexity is not good

Here we need to use data structure of segment tree. We should support two kind of operations:

1. add a number to the interval represented by the node of segment tree
2. add a number to the part of interval represented by the node of segment tree

The difference is if the interval that need add a number is covered the interval represented by the node of segment tree, then we record it in the node’s some data. If the interval covered part of the interval represented by the node, then we record it in the node’s another data, and continue to add number to children of the node if needed

Solution

#include <cstdio>
#include <algorithm>
const int DAT_SIZE = (1 << 18) - 1;
using namespace std;
int N, Q;
long long data[DAT_SIZE];
long long datb[DAT_SIZE];
void add(int a, int b, int x, int k, int l, int r) {
  if (a <= l && r <= b) {
    data[k] += x;
  } else if (l < b && a < r) {
    datb[k] += (min(b, r) - max(a, l)) * x;
    add(a, b, x, k * 2 + 1, l, (l + r) / 2);
    add(a, b, x, k * 2 + 2, (l + r) / 2, r);
  }
}
long long sum(int a, int b, int k, int l, int r) {
  if (b <= l || r <= a) {
    return 0;
  } else if (a <= l && r <= b) {
    return data[k] * (r - l) + datb[k];
  } else {
    long long res = (min(b, r) - max(a, l)) * data[k];
    res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
    res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
return res;
  }
}
int main(int argc, char *argv[]) {
  memset(data, 0, sizeof(data));
  memset(datb, 0, sizeof(datb));
  scanf("%d%d", &N, &Q);
  getchar();
  for (int i = 0; i < N; ++i) {
    int a;
    scanf("%d", &a);
    add(i, i+1, a, 0, 0, N);
  }
  getchar();
  for (int i = 0; i < Q; ++i) {
    char T[2];
    scanf("%1s", T);
    int L, R, X;
    if (T[0] == 'C') {
      scanf("%d%d%d", &L, &R, &X);
      add(L - 1, R, X, 0, 0, N);
    } else if (T[0] == 'Q') {
      scanf("%d%d", &L, &R);
      printf("%lld\n", sum(L - 1, R, 0, 0, N));
    }
    getchar();
  }
return 0;
}

time complexity is O(lgN)

space complexity is O(N)