树状数组模版

树状数组是一种类似于线段树的数据结构，它的功能主要借助于三个函数（也可以说是两个）来完成：

1.lowbit

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

用来计算二进制位数，之后的两个函数都会用到。

2.add（单点修改、区间修改）

void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x); } }

单点修改直接调用，区间（x,y)修改等于：x到n+修改值，y+1到n-修改值

3.query(单点查询，区间查询）

int query(int x) { int sum=0; while(x!=0) { sum+=tree[x]; x-=lowbit(x); } return sum; }

单点查询直接调用，区间查询相当于求一个前缀和，用1——y减去1——x即可。

完整代码：

#include<cstdio> using namespace std; int tree[500010],input[500010]; int n,m; int lowbit(int k) { return k & -k; } void add(int x,int k) { while(x<=n) { tree[x]+=k; x+=lowbit(x); } } int query(int x) { int sum=0; while(x!=0) { sum+=tree[x]; x-=lowbit(x); } return sum; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&input[i]); for(int i=1,a,b,c,d;i<=m;i++) { scanf("%d",&a); if(a==1) { scanf("%d%d%d",&b,&c,&d); add(b,d); add(c+1,-d); } if(a==2) { scanf("%d",&b); printf("%d\n",query(b)+input[b]); } } return 0; }

 

转载于:https://www.cnblogs.com/charlesss/p/10588187.html

相关资源：25个经典网站源代码