首页 > 其他 > 详细

POJ3468 A Simple Problem With Integers 树状数组 区间更新区间询问

时间:2014-02-19 17:48:29      阅读:257      评论:0      收藏:0      [点我收藏+]

今天学了很多关于树状数组的技巧。一个是利用树状数组可以简单的实现段更新,点询问(二维的段更新点询问也可以),每次修改只需要修改2个角或者4个角就可以了,另外一个技巧就是这题,原本用线段树做,现在可以用树状数组做的题,只需多维护一个bit即可。具体的思路见下面的链接:

http://hi.baidu.com/billdu/item/053f6a15ca301b0a8ebde400

要理解里面的橙色块求的时候是打竖看的,不是打横看的。

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
60
61
62
63
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#define ll long long
#define maxn 100000
#define lowbit(k) k&(-k)
using namespace std;
 
ll bit[2][maxn + 50];
int n,q;
 
void inc(ll bit[],int i, int m)
{
    for (; i <= n; i += lowbit(i)) bit[i] += m;
}
 
ll query(ll bit[],int i)
{
    ll sum = 0;
    for (; i > 0; i -= lowbit(i)){
        sum += bit[i];
    }
    return sum;
}
 
ll sum[maxn + 50];
 
int main()
{
    while (cin >> n >> q)
    {
        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= n; i++){
            scanf("%lld", sum + i);
        }
        sum[0] = 0;
        for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
        char str[3];
        int a,b,c;
        for (int i = 0; i < q; i++){
            scanf("%s", str);
            if (str[0] == ‘Q‘){
                scanf("%d%d", &a, &b);
                ll ans = (query(bit[0], b)*(b + 1) - query(bit[1], b)) - (query(bit[0], a - 1)*a - query(bit[1], a - 1));
                ans += sum[b] - sum[a - 1];
                printf("%lld\n", ans);
            }
            else{
                scanf("%d%d%d", &a, &b, &c);
                inc(bit[0], a, c);
                inc(bit[1], a, c*a);
                inc(bit[0], b + 1, -c);
                inc(bit[1], b + 1, -c*(b + 1));
            }
        }
    }
    return 0;
}

POJ3468 A Simple Problem With Integers 树状数组 区间更新区间询问

原文:http://www.cnblogs.com/chanme/p/3555084.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!