POJ 3468 A Simple Problem with Integers【线段树/树状数组】

树状数组：每次一看题解就是bits维护一发，是时候来学习这个玩意了（说不定跟网络流一样，学了就考哈哈哈）

原理：

当理解了线段树之后，想要理解树状数组：就是相当于把右边那一部分删掉（因为右边的可以由整体减去左边的来算出来）

精华在图上，【挑战程序设计竞赛】对原理还是讲解得挺明白的！

用法：

最简单而且常见的用法就是处理前缀和：

可以做到的是：O（logn）维护单点更新，O（logn）求前缀和

代码：

#include<bits/stdc++.h>
using namespace std;

#define LL __int64

const int maxn=1e5+50;

int n,m;
LL c[maxn],x;

int lowbit(int x){
    return x&(-x);
}

void add(LL c[],int pos,LL num){
    while(pos<=n){
        c[pos]+=num;
        pos+=lowbit(pos);
    }
}

LL sum(LL c[],int pos){
    LL ret=0;
    while(pos){
        ret+=c[pos];
        pos-=lowbit(pos);
    }
    return ret;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        add(c,i,x);
    }
    scanf("%d",&m);
    int l,r;
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%lld\n",sum(c,r)-sum(c,l-1));
    }
    return 0;
}

针对这个题

上一发我泰神的讲解，思路足够清楚明白：

膜拜泰神

理解为什么要两个树状数组？

很简单：在数学计算之后，发现有常数值，也有一次项。那么用两个树状数组分别维护就好

代码如下：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<algorithm>
using namespace std;

#define LL long long

const int maxn=1e5+50;
LL c1[maxn],c2[maxn];
char s[5];
int n,m;

int lowbit(int x){
    return x&(-x);
}

void add(LL c[],int pos,LL num){
    while(pos<=n){
        c[pos]+=num;
        pos+=lowbit(pos);
    }
}

LL sum(LL c[],int pos){
    LL ret=0;
    while(pos){
        ret+=c[pos];
        pos-=lowbit(pos);
    }
    return ret;
}

LL getans(int x){
    return sum(c1,x)+(x+1)*sum(c2,x);
}

int main(){
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        LL x;
        int u,v;
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            add(c1,i,x);
        }
        while(m--){
            scanf("%s",s);
            scanf("%d%d",&u,&v);
            if (s[0]=='Q'){
                printf("%lld\n",getans(v)-getans(u-1));
            }
            else{
                scanf("%lld",&x);
                add(c1,u,-x*u);
                add(c1,v+1,x*(v+1));
                add(c2,u,x);
                add(c2,v+1,-x);
            }
        }
    }
    return 0;
}