luogu P3374 【模板】树状数组 1
在大牛分站交能过，主站卡常。
时间复杂度为 n√n ≈ 3.5 * 108，我都不知道怎么过的。。
——代码
1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 5 using namespace std; 6 7 const int MAXN = 500001; 8 int n, m, S, C; 9 int a[MAXN], st[MAXN], ed[MAXN], belong[MAXN], sum[MAXN]; 10 11 inline void init() 12 22 for(i = 1; i <= C; i++) 23 for(j = st[i]; j <= ed[i]; j++) 24 sum[i] += a[j], belong[j] = i; 25 } 26 27 inline void update(int x, int k) 28 32 33 inline int query(int x, int y) 34 41 for(i = x; i <= ed[l]; i++) ans += a[i]; 42 for(i = l + 1; i <= r 1; i++) ans += sum[i]; 43 for(i = st[r]; i <= y; i++) ans += a[i]; 44 return ans; 45 } 46 47 inline void work() 48 56 } 57 58 int main() 59View Code
luoguP3368 【模板】树状数组 2
在大牛分站交能过，主站卡常。
——代码
1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 5 using namespace std; 6 7 const int MAXN = 500001; 8 int n, m, S, C; 9 int a[MAXN], belong[MAXN], add[MAXN], st[MAXN], ed[MAXN]; 10 11 inline void init() 12 22 for(i = 1; i <= C; i++) 23 for(j = st[i]; j <= ed[i]; j++) 24 belong[j] = i; 25 } 26 27 inline void update(int x, int y, int k) 28 35 for(i = x; i <= ed[l]; i++) a[i] += k; 36 for(i = l + 1; i <= r 1; i++) add[i] += k; 37 for(i = st[r]; i <= y; i++) a[i] += k; 38 } 39 40 inline void work() 41 51 else printf("%d\n", a[x] + add[belong[x]]); 52 } 53 } 54 55 int main() 56View Code
luoguP3372 【模板】线段树 1
这个数据水，主站就能过。
——代码
1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #define LL long long 5 6 using namespace std; 7 8 const int MAXN = 100001; 9 int n, m, S, C; 10 int st[MAXN], ed[MAXN], belong[MAXN]; 11 LL a[MAXN], sum[MAXN], add[MAXN]; 12 13 inline void init() 14 24 for(i = 1; i <= C; i++) 25 for(j = st[i]; j <= ed[i]; j++) 26 sum[i] += a[j], belong[j] = i; 27 } 28 29 inline void update(int x, int y, LL k) 30 38 for(i = x; i <= ed[l]; i++) a[i] += k; 39 sum[l] += (ed[l] x + 1) * k; 40 for(i = l + 1; i <= r 1; i++) 41 45 for(i = st[r]; i <= y; i++) a[i] += k; 46 sum[r] += (y st[r] + 1) * k; 47 } 48 49 inline LL query(int x, int y) 50 58 for(i = x; i <= ed[l]; i++) ans += a[i] + add[l]; 59 for(i = l + 1; i <= r 1; i++) ans += sum[i]; 60 for(i = st[r]; i <= y; i++) ans += a[i] + add[r]; 61 return ans; 62 } 64 inline void work() 65 76 else printf("%lld\n", query(x, y)); 77 } 78 } 79 80 int main() 81View Code
luogu P3373 【模板】线段树 2
看了黄学长的讲解，猛然醒悟！%%%%%hzwer
整块可以直接打标记，而左右两边零散的块要先把它们所属于的整块的标记清除掉再打，否则会错。
——代码
1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #define LL long long 5 6 using namespace std; 7 8 const int MAXN = 100001; 9 int n, m, p, S, C; 10 int st[MAXN], ed[MAXN], belong[MAXN]; 11 LL a[MAXN], sum[MAXN], add[MAXN], mul[MAXN]; 12 13 inline void init() 14 25 for(i = 1; i <= C; i++) 26 for(j = st[i]; j <= ed[i]; j++) 27 sum[i] += a[j], belong[j] = i; 28 } 29 30 inline void reset(int x) 31 38 39 inline void update(int f, int x, int y, LL k) 40 51 if(f == 1) sum[l] = (sum[l] + tot * (k 1)) % p; 52 else sum[l] = (sum[l] + (y x + 1) * k) % p; 53 return; 54 } 55 56 reset(l); 57 for(tot = 0, i = x; i <= ed[l]; i++) 58 62 if(f == 1) sum[l] = (sum[l] + tot * (k 1)) % p; else sum[l] = (sum[l] + (ed[l] x + 1) * k) % p; 64 65 reset(r); 66 for(tot = 0, i = st[r]; i <= y; i++) 67 71 if(f == 1) sum[r] = (sum[r] + tot * (k 1)) % p; 72 else sum[r] = (sum[r] + (y st[r] + 1) * k) % p; 73 74 for(i = l + 1; i <= r 1; i++) 75 if(f == 1) 76 80 else add[i] = (add[i] + k) % p; 81 } 82 83 inline LL query(int x, int y) 84 93 for(i = x; i <= ed[l]; i++) 94 ans = (ans + a[i] * mul[l] + add[l]) % p; 95 for(i = l + 1; i <= r 1; i++) 96 ans = (ans + sum[i] * mul[i] + add[i] * (ed[i] st[i] + 1)) % p; 97 for(i = st[r]; i <= y; i++) 98 ans = (ans + a[i] * mul[r] + add[r]) % p; 99 return ans; 100 } 101 102 inline void work() 103 112 } 113 114 int main() 115View Code
还有一个链接，黄学长的分块姿势。
【分块】数列分块入门19 by hzwer
上一篇：[BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）
下一篇：[luoguP1962] 斐波那契数列（矩阵快速幂）
分块 树状数组 线段树 模板
