HDOJ 1166 树状数组

87 阅读 0 评论 58 点赞

我是靠谱客的博主活泼招牌，这篇文章主要介绍HDOJ 1166 树状数组，现在分享给大家，希望可以做个参考。

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1166、

这题以前写过。不过用的是线段树。今天了解了一下树状数组。就用这个方法重新做了一下。

特点就是lowbit函数。本来自己在草稿纸上拆解了一下树状数组的过程但是因为不知道为什么上传不了图片就没办法了。emm。其实这个就是公式C[i] = A[i+2^k-1]+A[i+2^k-2]+…..A[1]。k就是和i的二进制码的低位到高位的连续0的数量。就是用lowbit函数来判断。

复制代码

1
2
3
int lowbit(int i){
    return i&(-1);
}

这里运用了计算机里的补码运算了。
然后因为有了这个公式update也就很简单了。同理query也是一样的。
直接上代码

复制代码

#include<bits/stdc++.h>
#define PI 3.1415926
#define INF 1e18
#define inf 1e9
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int _max=50005;
int a[_max],n;
int lowbit(int i){
    return i&(-i);
}
void update(int i,int val){
    while(i <= n){
        a[i] += val;
        i += lowbit(i);
    }
}
int sum(int i){
    int sum = 0;
    while(i > 0){
        sum += a[i];
        i -= lowbit(i);
    }
    return sum ;
}
int main(){
    IOS;
    int t;
    cin>>t;
    for(int Cas = 1 ; Cas <= t ; Cas++){
        int val;
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i = 1 ; i <= n ; i++){
            cin>>val;
            update(i,val);
        }
        cout<<"Case "<<Cas<<":"<<endl;
        string s;
        while(cin>>s){
            int j,k;
            if(s[0]=='E') break;
            cin>>j>>k;
            if(s[0]=='A') update(j,k);
            else if(s[0]=='S') update(j,-k);
            else cout<<sum(k)-sum(j-1)<<endl;
        }
    }
    return 0;
}

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
#include<bits/stdc++.h>
#define PI 3.1415926
#define INF 1e18
#define inf 1e9
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std ;
typedef long long ll;
typedef unsigned long long ull;
const int _max=50005;
int a[_max],n;
int lowbit(int i){
    return i&(-i);
}
void update(int i,int val){
    while(i <= n){
        a[i] += val;
        i += lowbit(i);
    }
}
int sum(int i){
    int sum = 0;
    while(i > 0){
        sum += a[i];
        i -= lowbit(i);
    }
    return sum ;
}
int main(){
    IOS;
    int t;
    cin>>t;
    for(int Cas = 1 ; Cas <= t ; Cas++){
        int val;
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i = 1 ; i <= n ; i++){
            cin>>val;
            update(i,val);
        }
        cout<<"Case "<<Cas<<":"<<endl;
        string s;
        while(cin>>s){
            int j,k;
            if(s[0]=='E') break;
            cin>>j>>k;
            if(s[0]=='A') update(j,k);
            else if(s[0]=='S') update(j,-k);
            else cout<<sum(k)-sum(j-1)<<endl;
        }
    }
    return 0;
}