【模板】树状数组

单点更新 + 区间查询洛谷P3374 树状数组1

讲的很清晰易懂qwq
接下来让我胡乱总结一下qwq(主要是存一下这几张图hhh)

　　　　树状数组基于二进制的思想

　　2.add函数从x到n ask_sum函数从x到0 //因为改变sum[i]要从下往上修改询问区间和要从大的sum[i]向小的加

　　3.然后贴代码qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 #define sz 500050
 4 using namespace std;
 5 int n,m;
 6 int num[sz],sum[sz];
 7 int lowbit(int x) {return x&(-x);}
 8 int add(int x,int y) {
 9     while(x <= n) {
10         sum[x] += y;
11         x += lowbit(x);
12     }
13 }//模板2 用for写的qwq
14 int build(int x) { 
15     for(int i = 1; i <= x; i++) {
16         scanf("%d",&num[i]);
17         add(i,num[i]);
18     }
19 }
20 int ask_sum(int x) {
21     int a = 0;
22     while(x > 0) {
23         a += sum[x];
24         x -= lowbit(x);
25     }
26     return a;
27 }
28 int main() {
29     scanf("%d%d",&n,&m);
30     build(n);
31     int pd,x,y,ans;
32     for(int i = 1; i <= m; i++) {
33         scanf("%d%d%d",&pd,&x,&y);
34         if(pd == 1) add(x,y);
35         else {
36             if(x > y) swap(x,y);
37             ans = ask_sum(y) - ask_sum(x-1);
38             printf("%d
",ans);
39         }
40     }
41     return 0;
42 }

　2. 树状数组 2 ---- 区间修改+单点查询洛谷P3368 树状数组2

需要用到差分的思想qwq 例图摘自洛谷题解
别的就没什么啦
//用while写的时候有一句x -= lowbit(x) 写成了c[x] -= lowbit(x) 就死循环啦
所以我还是老老实实用for写吧QAQ

　　　　代码君qwq

 1 #include<cstdio>
 2 #include<iostream>
 3 #define sz 500050
 4 using namespace std;
 5 int n,m,c[sz];
 6 int lowbit(int x) {return x&(-x);}
 7 void add(int x, int y) {for(int i = x; i <= n; i+=lowbit(i)) c[i] += y; }
 8 int ask(int x) {
 9     int ans = 0;
10     for(int i = x; i > 0; i -=lowbit(i)) ans += c[i];
11     return ans;
12 }
13 int main() {
14     scanf("%d%d",&n,&m);
15     int pd,x,y,k,a,now = 0;
16     for(int i = 1; i <= n; i++) {
17         scanf("%d",&a);
18         add(i,a - now);
19         now = a;
20     }
21     for(int i = 1; i <= m; i++) {
22         scanf("%d%d",&pd,&x);
23         if(pd == 1) {
24             scanf("%d%d",&y,&k);
25             add(x,k), add(y+1,-k);
26         }
27         else printf("%d
",ask(x));
28     }    
29     return 0;
30 }

　记录一下我的zz实验qwq

　　洛谷P3368 树状数组2

把build函数写进主函数内672ms（for）
build函数单独写 673ms（for）
build函数单独写（add ask 函数用while） 676ms
好像基本上没有什么差别qwq

总之岁月漫长，然而值得期待。

【模板】 树状数组

【模板】树状数组