题解：P3374 【模板】树状数组 1

Alexchen0704 · 2025-03-21 19:23:12 · 题解

P3374 【模板】树状数组 1（单点修改，区间查询）

铺垫

我们知道，一个数可以分解成多个 2^n 形式的数，也就是说，我们如果要求一个数组前 x 个数的和，例如我们要求出前六个数的和，只用求出从 2^0=1 长度为 2^2=4 的和与从 2^2+1=5 长度为 2 的和并相加就可以求出前六个数的和。

我们知道，6=(110)_2 也就是 (10)_2+(100)_2 所以我们只需要求出一个数二进制的末尾 0 的数量就可以进行拆分从而显著提高查找效率，这里就要引用 int lowbit(int n){return n&(-n);}。也就是求一个数二进制末位的 1 加上若干个连续的 0 的二进制数的数值。

实现方法

我们可以构建一个如上图的树状数组，很显然，当一个编号为 n 的节点改变时，编号为 n+\operatorname{lowbit}(n) 的节点也要相应改变。因此，我们便将编号为 n+\operatorname{lowbit}(n) 的节点称为编号为 n 的节点的后继。

以样例为例，我们就可以得到一个这样的初始树状数组。也就是说，一个节点的值是他所有以这个节点为后继的节点的数值之和。修改也同理，只需要将需要修改的节点的所有后继修改就可以了。这样我们就可以得到修改函数了，平均时间复杂度为 O(\log n)。

void g(int now,int x){
    if(now>n) return;
    f[now]+=x;
    g(now+lowbit(now),x);
}

查询也同理，如果我们要查询（初始数组）前三个数的和，只需要将树状数组中第二个节点的值与第三个节点的值相加，也就是 6+4=1+5+4=10，换言之，我们只需要一直往前搜索编号为 n 的节点前驱也就是编号为 n-\operatorname{lowbit}(n) 的数值并求和就是前 n 个数的和。

unsigned long long co(int x){return x>0?co(x-lowbit(x))+f[x]:0;}

AC代码

#include <bits/stdc++.h>
using namespace std;
unsigned long long f[100000005],n,w,a,b,c,t;
int lowbit(int n){return n&(-n);}
void g(int now,int x){
    if(now>n) return;
    f[now]+=x;
    g(now+lowbit(now),x);
}
unsigned long long co(int x){return x>0?co(x-lowbit(x))+f[x]:0;}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>t;
        g(i,t);
    }
    for(int i=0;i<w;i++){
        cin>>a>>b>>c;
        if(a==1){
            g(b,c);
        }else{
            cout<<co(c)-co(b-1)<<endl;
        }
    }
    return 0;
}