- 基本介绍
- 模板题目
- 代码实现
基本介绍
这篇是树状数组模板1 主要内容有:
1.将某数加上x 2.求某区间和 也就是说支持单点修改模板题目
见基本介绍
代码实现
#include#include #include using namespace std; #define in = read() typedef long long ll; const ll size = 1000000 + 100; ll n,m,x,y,z; ll a[size],c[size];inline ll read(){ ll num = 0 , f = 1; char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') f = -1; ch = getchar(); } while(isdigit(ch)){ num = num*10 + ch - '0'; ch = getchar(); } return num*f;}inline ll lowbit(ll x){ return x&-x;}inline ll sum(ll x){ ll ans = 0; while(x){ ans += c[x]; x -= lowbit(x); } return ans;;}inline void add(ll x,ll y){ while(x <= n){ c[x] += y; x += lowbit(x); }}int main(){ n in; m in; for(int i=1;i<=n;i++){ a[i] in; add(i,a[i]); } for(int i=1;i<=m;i++){ z in; x in; y in; if(z == 1) add(x,y); if(z == 2) printf("%d\n",sum(y) - sum(x - 1)); }}//COYG