POJ - 3468 树状数组的区间更新与区间查询

发表于 | 更新于 | 分类于 | 阅读次数：

题目链接：A Simple Problem with Integers

思路

典型的区间更新与区间查询，一般来说，对于区间更新应该用线段树，但是树状数组也能实现，由于他的代码比较短，所以我一般选择树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll N,tree1[100001],tree2[100001];
ll a[100001];
int lowbit(int x)
{
    return (x&(-x));
}
 void update(ll x ,ll val)
{
    ll i;
    for( i = x ; i <= N;i+=lowbit(i) )
    {
        tree1[i]+=val;
        tree2[i]+=x*val;
    }
}
ll query(ll x)
{
    ll i;
    ll sum=0;
    for( i = x ; i > 0 ;i-=lowbit(i))
    {
        sum+=(x+1)*tree1[i]-tree2[i];
    }
    return sum;
}
int main()
{
    ll  Q , i , A ,B , C;
    string s;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> Q;
    a[0]=0;
    for ( i = 1 ;i <= N ; i++)
    {
         cin >> a[i];
         update(i ,a[i]-a[i-1]);
    }
    for ( i = 1 ; i <= Q ; i ++)
    {
        cin >> s;
        if(s[0]=='Q')
        {
            cin >> A >> B ;
            cout << query (B)- query(A-1)<<endl;
        }
        else
        {
            cin >> A >> B >> C;
            update(A , C);
            update(B+1 ,-C );
        }
    }
}