树状数组
详细介绍：https://www.cnblogs.com/xenny/p/9739600.html
http://www.sohu.com/a/245746824_100201031
https://www.cnblogs.com/wkfvawl/p/9445376.html
单点更新、单点查询
传统数组可做
1.单点修改+区间查询
int n;//点的数量int a[50005],c[50005]; //对应原数组和树状数组int lowbit(int x){return x&(-x);}void updata(int i,int k){ //在i位置加上kwhile(i <= n){c[i] += k;i += lowbit(i);}}//求sum(x)就是a[x]的前缀和，想查询l~r区间的元素和只需要求出来sum(r)-sum(l-1)int getsum(int i){int res = 0;while(i > 0){res += c[i];i -= lowbit(i);}return res;}int main(){
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
}
模板题：
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>//单点修改加区间查询using namespace std;int n;int a[50005],c[50005]; //对应原数组和树状数组int lowbit(int x){return x&(-x);}void updata(int i,int k){ //在i位置加上kwhile(i <= n){c[i] += k;i += lowbit(i);}}//求sum(x)就是a[x]的前缀和，想查询l~r区间的元素和只需要求出来sum(r)-sum(l-1)int getsum(int i){int res = 0;while(i > 0){res += c[i];i -= lowbit(i);}return res;}int main(){int T;scanf("%d",&T);for(int i=1;i<=T;i++){scanf("%d",&n);memset(a, 0, sizeof a);memset(c, 0, sizeof c);for(int i=1;i<=n;i++){scanf("%d",&a[i]);updata(i,a[i]);}printf("Case %d:\n",i);char s[10];while(cin>>s){if(s[0]=='Q'){//区间查询int l,r;scanf("%d%d",&l,&r);cout<<getsum(r)-getsum(l-1)<<endl;}if(s[0]=='A'){//单点增加 第x个数加tint x,t;scanf("%d%d",&x,&t);updata(x,t);}if(s[0]=='S'){//单点减少 第x个数减tint x,t;scanf("%d%d",&x,&t);updata(x,-1*t);}if(s[0]=='E')//结束break;}}}
HDU - 1166
2.区间修改+单点查询
int n,m;int a[50005] = {0},c[50005]; //对应原数组和树状数组int lowbit(int x){return x&(-x);}void updata(int i,int k){ //在i位置加上kwhile(i <= n){c[i] += k;i += lowbit(i);}}int getsum(int i){ //求D[1 - i]的和，即A[i]值int res = 0;while(i > 0){res += c[i];i -= lowbit(i);}return res;}int main(){cin>>n;memset(a,0,sizeof(a));memset(c,0,sizeof(c));for(int i = 1; i <= n; i++){cin>>a[i];updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值}//[x,y]区间内加上kupdata(x,k); //A[x] - A[x-1]增加kupdata(y+1,-k); //A[y+1] - A[y]减少k//查询i位置的值int sum = getsum(i);return 0;}
例题：P3368 【模板】树状数组 2 https://www.luogu.org/problem/show?pid=3368
1 #include<iostream>2 #include<cstdio>3 #include<cmath>4 #include<cstring>5 #include<algorithm>6 //单点修改加区间查询7 using namespace std;8 int n,m;9 int a[500005] = {0},c[500005]; //对应原数组和树状数组1011 int lowbit(int x){12 return x&(-x);13 }1415 void updata(int i,int k){ //在i位置加上k16 while(i <= n){17 c[i] += k;18 i += lowbit(i);19 }20 }2122 int getsum(int i){ //求D[1 - i]的和，即A[i]值23 int res = 0;24 while(i > 0){25 res += c[i];26 i -= lowbit(i);27 }28 return res;29 }3031 int main(){32 int m;33 cin>>n>>m;34 memset(a,0,sizeof(a));35 memset(c,0,sizeof(c));36 for(int i = 1; i <= n; i++){37 cin>>a[i];38 updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值39 }40 for(int i=1;i<=m;i++)41 {42 int t;43 cin>>t;44 if(t==1)45 {46 int x,y,k;47 cin>>x>>y>>k;48 //[x,y]区间内加上k49 updata(x,k); //A[x] - A[x-1]增加k50 updata(y+1,-k); //A[y+1] - A[y]减少k51 }52 else53 {54 int kk;55 cin>>kk;56 //查询i位置的值57 int sum = getsum(kk);58 cout<<sum<<endl;59 }60 }61 return 0;62 }
3.区间修改+区间查询
int n,m;int a[50005] = {0};int sum1[50005]; //(D[1] + D[2] + ... + D[n])int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])int lowbit(int x){return x&(-x);}void updata(int i,int k){int x = i; //因为x不变，所以得先保存i值while(i <= n){sum1[i] += k;sum2[i] += k * (x-1);i += lowbit(i);}}int getsum(int i){ //求前缀和int res = 0, x = i;while(i > 0){res += x * sum1[i] - sum2[i];i -= lowbit(i);}return res;}int main(){cin>>n;for(int i = 1; i <= n; i++){cin>>a[i];updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值}//[x,y]区间内加上kupdata(x,k); //A[x] - A[x-1]增加kupdata(y+1,-k); //A[y+1] - A[y]减少k//求[x,y]区间和int sum = getsum(y) - getsum(x-1);return 0;}
例题：https://vjudge.net/problem/POJ-3468
1 #include<iostream>2 #include<cstdio>3 #include<cmath>4 #include<cstring>5 #include<algorithm>6 //单点修改加区间查询7 using namespace std;8 #define ll long long9 int n,m;10 ll a[100005] = {0};11 ll sum1[100005]; //(D[1] + D[2] + ... + D[n])12 ll sum2[100005]; //(1*D[1] + 2*D[2] + ... + n*D[n])1314 int lowbit(int x){15 return x&(-x);16 }1718 void updata(int i,ll k){19 int x = i; //因为x不变，所以得先保存i值20 while(i <= n){21 sum1[i] += k;22 sum2[i] += k * (x-1);23 i += lowbit(i);24 }25 }2627 ll getsum(int i){ //求前缀和28 ll res = 0, x = i;29 while(i > 0){30 res += x * sum1[i] - sum2[i];31 i -= lowbit(i);32 }33 return res;34 }3536 int main(){37 int Q;38 ios_base::sync_with_stdio(false);39 cin.tie(0);40 cout.tie(0);41 cin>>n>>Q;42 for(int i = 1; i <= n; i++){43 cin>>a[i];44 updata(i,a[i] - a[i-1]); //输入初值的时候，也相当于更新了值45 }4647 for(int i=1;i<=Q;i++)48 {49 char c;50 cin>>c;51 if(c=='Q')52 {53 int x,y;54 cin>>x>>y;55 long long sum = getsum(y) - getsum(x-1);56 cout<<sum<<endl;57 }58 else59 {60 int x,y;61 ll k;62 cin>>x>>y>>k;63 //[x,y]区间内加上k64 updata(x,k); //A[x] - A[x-1]增加k65 updata(y+1,-k); //A[y+1] - A[y]减少k66 }67 }68 return 0;69 }
转载于
//www.cnblogs.com/Aiahtwo/p/11331107.html
我不是女神ヾ
小鱼儿
朱雀
忘是亡心i
ゞ 浴缸里的玫瑰
还没有评论，来说两句吧...