树状数组（Binary Indexed Tree(BIT), Fenwick Tree） 是一个查询和修改的复杂度都为 log(n)log(n) 的数据结构。
#include<iostream> #include<cstdio> #include<cmath> #include<string> using namespace std; int n,m,a[500009],c[500009],x,y,t; int command; int lowbit(int x) { return x&(-x); // 取 lowbit 的函数 // lowbit(1000100) = 100 // lowbit(1101010) = 10 } int sum(int x) { int ans=0; for(int i = x; i > 0; i -= lowbit(i)) ans=ans+c[i]; // 从C数组中取值 return ans; } void modify(int x,int d) { for(int i = x;i <= n;i += lowbit(i)) c[i] += d; // 区间加法操作，维护前缀和 /*********************************************** * 格外注意，BIT树状数组的元素下标从 1 开始， * * 在访问的时候，如上面的遍历，就是 <= n， * * sum 函数中的 i 的范围，也是 >0 * * 具体的下标访问范围应该为 [1, n] * ************************************************/ } int main() { scanf("%d%d",&n,&m); // 序列数的个数 操作次数 for(int i=1;i<=n;i++) { scanf("%d",&a[i]); // 读序列的数 modify(i,a[i]); // 区间操作，维护C数组 } for(int i=1;i<=m;i++) { scanf("%d%d%d",&command,&x,&y); // 操作数 or 区间左右的值 if(command == 1) modify(x,y); // 读入了 add 给序列第 x 个数增加 y if(command == 2) printf("%d\n",sum(y)-sum(x-1)); // 读入了 check 输出从第 x 个数到第 y 个数的和 } return 0; } NOIP 211 天打卡
