洛谷 P3374 [模板] 树状数组 1
单点修改, 区间查值. 细节看代码
代码:
- #include <bits/stdc++.h>
- #define nmax 500010
- using namespace std;
- int n,m;
- int a[nmax],qz[nmax]={0},c[nmax];
- inline int lowb(int x){ return x&(-x); }
- void build(){
- cin>>n>>m;
- for (int i=1; i<=n; i++) {
- scanf("%d",&a[i]);
- qz[i]=qz[i-1]+a[i];
- c[i]=qz[i]-qz[i-lowb(i)];
- }
- }
- inline void add(int x,int k){
- a[x]+=k; // 这里 x+=lowb(x) 是走向它父亲节点所以先加后走, 判断时是 x<=n
- while(x<=n) { c[x]+=k; x+=lowb(x); }
- }
- inline int findqz(int x){ // 求 1~x 的和
- int ans=0;
- while(x) { ans+=c[x]; x-=lowb(x); }
- return ans;
- }
- inline int query(int x,int y) { return findqz(y)-findqz(x-1); }
- int main(){
- build();
- int b,x,y;
- for (int i=0; i<m; i++) {
- scanf("%d%d%d",&b,&x,&y);
- if(b==1) add(x,y);
- else printf("%d\n",query(x,y));
- }
- return 0;
- }
写树状数组的感觉比写线段树的感觉好多了~ 在家里一个人打线段树好无聊, 都没有朋友玩, 没有女仔玩. 打了树状数组发现个个都是位运算, 行数又少, 超喜欢树状数组的.
洛谷 P3368 [模板] 树状数组 2
区间修改 (区间加), 单点查值.
代码:
- #include <bits/stdc++.h>
- #define nmax 500010
- using namespace std;
- int n,m;
- int a[nmax],c[nmax]={0};
- inline int lowb(int x){ return x&(-x); }
- inline void ta(int x,int k){ // 把 1~x 的 c[i] 都加上 k
- while(x) { c[x]+=k; x-=lowb(x); }
- }
- inline void add(int x,int y,int k){
- ta(x-1,-k);
- ta(y,k);
- }
- inline int query(int x) {
- int tot=a[x]; // 得在 x 还没有变的时候把 a[x] 给加上
- while(x<=n) { tot+=c[x]; x+=lowb(x); }
- return tot;
- }
- int main(){
- cin>>n>>m;
- for (int i=1; i<=n; i++) scanf("%d",&a[i]);
- int b,x,y,k;
- for (int i=0; i<m; i++) {
- scanf("%d",&b);
- if(b==1) {
- scanf("%d%d%d",&x,&y,&k);
- add(x,y,k);
- }
- else { scanf("%d",&x); printf("%d\n",query(x)); }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3140067.html