【洛谷P3374 P3368】树状数组

本文主要是介绍【洛谷P3374 P3368】树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示

本文只记录模板，不做详细解释

P3374 树状数组1

原题链接

#include <iostream>
#define lowbit(x) x&(-x)
#define N 5*(int)1e5+1
using namespace std;
int n,m,num[N];
long long tree[N];
void add(int idx,int val){while(idx<=n){tree[idx]+=val;idx+=lowbit(idx);}
}
long long sum(int idx){long long ret=0;while(idx){ret+=tree[idx];idx-=lowbit(idx);}return ret;
}
int main() {scanf("%d%d",&n,&m);fill(tree,tree+n+1,0);for(int i=1;i<=n;i++){scanf("%d",&num[i]);add(i,num[i]);}for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(x==1){add(y,z);}else{printf("%lld\n",sum(z)-sum(y-1));}}return 0;
}

P3368 树状数组2

原题链接

#include <iostream>
#define lowbit(x) x&(-x)
#define N 5*(int)1e6+1
using namespace std;
int n,m,num[N];
long long tree[N];
void add(int idx,int val){while(idx<=n){tree[idx]+=val;idx+=lowbit(idx);}
}
long long sum(int idx){long long ret=0;while(idx){ret+=tree[idx];idx-=lowbit(idx);}return ret;
}
int main() {scanf("%d%d",&n,&m);fill(tree,tree+n+1,0);for(int i=1;i<=n;i++){scanf("%d",&num[i]);add(i,num[i]-num[i-1]);}for(int i=1;i<=m;i++){int c,l,r,k;scanf("%d",&c);if(c==1){scanf("%d%d%d",&l,&r,&k);add(l,k);add(r+1,-k);}else{scanf("%d",&k);printf("%lld\n",sum(k));}}return 0;
}
/*
差分
设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}
也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+....+b[i];(这个很好证的)。
假如区间[2,4]都加上2的话
a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};
发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.
所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:
b[x]=b[x]+k;b[y+1]=b[y+1]-k;
*/