首页 > 代码库 > 树状数组—模板整理
树状数组—模板整理
树状数组整理
update 更新
1.单点更新，将第p个数增加v
1 void update(int p,int v) //将第P个数增加v 2 {3 while(p<=n)4 {5 sum[p] += v;6 p += lowbit(p); 7 } 8 }
2.区间更新，将区间[x,y]增加v
1 void inerval_update(int x,int y,int v) //区间修改—[x,y]的区间增加v 2 {3 update(x,v);4 update(y+1,-v);5 }
或者直接在输入时加上这两行代码，下面有
附：单点改变，将第p个数变成v，还要定义一个储存初始值的数组a。
1 void modify(int p,int v) //将第p个数变成v 2 {3 int d = v - a[p]; //d表示 增加了多少 4 while(p<=n)5 {6 sum[p] += d;7 p+=lowbit(p);8 }9 }
query 查询
1.单点查询，查询第p个点的值
1 int query(int p) //查询第p个点的值是多少 2 { 3 int ans=0; 4 while(p) 5 { 6 ans += sum[p]; 7 p -= lowbit(p); 8 } 9 return ans;10 }
2.区间查询，查询区间[x,y]的值 （也可以在输入时直接加两行代码，下面有）
1 int interval_query(int x,int y) //查询区间[a,b]的值是多少 2 {3 return query(y) - query(x-1);4 }
合起来就成这样了
1 #include<iostream> 2 using namespace std; 3 4 const int N = 100100 ; 5 6 int n,m,a; 7 int ch,x,y,v; 8 int sum[N];//树状数组 9 10 int lowbit(int x) 11 {12 return x&(-x);13 }14 15 void update(int p,int v) //将第P个数增加v 16 {17 while(p<=n)18 {19 sum[p] += v;20 p += lowbit(p); 21 } 22 } 23 24 int query(int p) //查询第p个点的值是多少 25 {26 int ans=0;27 while(p)28 {29 ans += sum[p];30 p -= lowbit(p);31 }32 return ans;33 }34 35 void interval_update(int x,int y,int v) //区间修改—[x,y]的区间增加v 36 {37 update(x,v);38 update(y+1,-v);39 } 40 41 int interval_query(int x,int y) //查询区间[a,b]的值是多少 42 {43 return query(y) - query(x-1);44 }45 46 int main()47 {48 cin>>n>>m;49 for (int i=1;i<=n;i++) 50 {51 cin>>a;52 update(i,a); //建树 53 }54 for (int i=1;i<=m;++i) 55 {56 cin>>ch;57 if (ch==1) //单点修改 58 {59 cin>>x>>y;60 update(x,y);61 }62 if (ch==2) //区间修改 63 {64 cin>>x>>y>>v;65 update(x,v);66 update(y+1,-v); //interval_update(x,y,v); 67 }68 if (ch==3) //单点查询 69 {70 cin>>x; 71 cout<<query(x); 72 }73 if (ch==4) //区间查询74 {75 cin>>x>>y; 76 cout<<query(y)-query(x-1)<<endl; //cout<<interval_query(x,y)77 } 78 }79 return 0;80 }81 /*82 //附 改变值 还需定义 a[] 记录初始值 83 void modify(int p,int v) //将第p个数变成v 84 {85 int d = v - a[p]; //d表示 增加了多少 86 while(p<=n)87 {88 sum[p] += d;89 p+=lowbit(p);90 }91 }92 */
树状数组—模板整理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。