poj3468 A Simple Problem with Integers

题意：

给定Q (1 ≤ Q ≤ 100,000)个数A1,A2 … AQ，以及可能多次进行的两个操作:
1)对某个区间Ai … Aj的每个数都加n(n可变）

2) 求某个区间Ai … Aj的数的和

思路：

线段树，节点存放原来的和sum和增量inc，节点区间[l, r)的和实际上是sum + inc * (r - l)。

在增加时，如果要加的区间正好覆盖一个节点，则增加其节点的inc值，不再往下走，否则要更新sum(加上本次增量),再将增量往下传。这样更新的复杂度就是O(log(n)) 。

在查询时，如果待查区间不是正好覆盖一个节点，就将节点的inc往下带，然后将inc代表的所有增量累加到sum上后将inc清0，接下来再往下查询。 inc往下带的过程也是区间分解的过程，复杂度也是O(log(n))。

实现：

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 typedef long long ll;
  5 
  6 const int MAXN = 131073;
  7 struct node
  8 {
  9     ll sum, inc;
 10 };
 11 
 12 node data[2 * MAXN - 1];
 13 
 14 int n, q;
 15 char c;
 16 ll x, y, z, tmp;
 17 void init(int n_)
 18 {
 19     n = 1;
 20     while (n < n_)
 21     {
 22         n <<= 1;
 23     }
 24     for (int i = 0; i < n; i++)
 25     {
 26         data[i].sum = data[i].inc = 0;
 27     }
 28 }
 29 
 30 void add(int a, int b, int k, int l, int r, ll num)
 31 {
 32     if (b <= l || a >= r)
 33         return;
 34     if (l >= a && r <= b)
 35     {
 36         data[k].inc += num;
 37         return;
 38     }
 39     ll len = 0;
 40     if (a >= l && b <= r)
 41         len = b - a;
 42     else if (l >= a)
 43         len = b - l;
 44     else
 45         len = r - a;
 46     data[k].sum += num * len;
 47     add(a, b, 2 * k + 1, l, (l + r) / 2, num);
 48     add(a, b, 2 * k + 2, (l + r) / 2, r, num);
 49 }
 50 
 51 ll query(int a, int b, int k, int l, int r, ll num)
 52 {
 53     data[k].inc += num;
 54     if (b <= l || a >= r)
 55     {
 56         return 0;
 57     }
 58     if (l >= a && r <= b)
 59     {
 60         return data[k].sum + (ll)(r - l) * data[k].inc;
 61     }
 62     if (data[k].inc)
 63     {
 64         data[k].sum += data[k].inc * (ll)(r - l);
 65     }
 66     ll tmp = data[k].inc;
 67     data[k].inc = 0;
 68     ll x = query(a, b, 2 * k + 1, l, (l + r) / 2, tmp);
 69     ll y = query(a, b, 2 * k + 2, (l + r) / 2, r, tmp);
 70     return x + y;
 71 }
 72 
 73 int main()
 74 {
 75     cin >> n >> q;
 76     int n_ = n;
 77     init(n);
 78     for (int i = 0; i < n_; i++)
 79     {
 80         scanf("%I64d", &tmp);
 81         getchar();
 82         add(i, i + 1, 0, 0, n, tmp);
 83     }
 84     for (int i = 0; i < q; i++)
 85     {
 86         scanf("%c", &c);
 87         if (c == 'C')
 88         {
 89             scanf("%I64d %I64d %I64d", &x, &y, &z);
 90             getchar();
 91             add(x - 1, y, 0, 0, n, z);
 92         }
 93         else
 94         {
 95             scanf("%I64d %I64d", &x, &y);
 96             getchar();
 97             ll res = query(x - 1, y, 0, 0, n, 0);
 98             printf("%I64d
", res);
 99         }
100     }
101     return 0;
102 }

总结：

还有离散化等技巧。