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函数来判断。

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;
} 

最后

以上就是活泼招牌为你收集整理的HDOJ 1166 树状数组的全部内容，希望文章能够帮你解决HDOJ 1166 树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。