树状数组是解决增加和查询的较好的方法时间复杂度均为logn
基础模板:
int lowbit(int x) { //求x对应的2的k次方(k为x转换为2进制最低位开始连续0的个数) return x & (-x); } void update(int i, int k) {//在i位置加k while(i <= N) { c[i] += k; i += lowbit(i); } } int getsum(int i) {//获得1-i数组元素的和 int res = 0; while(i > 0) { res += c[i]; i -= lowbit(i); } return res; }
来道裸题
单点更新,区间查询
#include <iostream> #include <cstdio> #include<cstdlib> #include<cstring> #include<string> using namespace std; const int MAXN = 50010; int a[MAXN]; int c[MAXN]; int N; int lowbit(int x) { //求x对应的2的k次方(k为x转换为2进制最低位开始连续0的个数) return x & (-x); } void update(int i, int k) {//在i位置加k while(i <= N) { c[i] += k; i += lowbit(i); } } int getsum(int i) {//获得1-i数组元素的和 int res = 0; while(i > 0) { res += c[i]; i -= lowbit(i); } return res; } int main () { int T; scanf("%d", &T); int num = 0; while(T--) { printf("Case %d: ", ++num); memset(a, 0, sizeof a); memset(c, 0, sizeof c); scanf("%d", &N); for(int i = 1; i <= N; ++i) { scanf("%d", &a[i]); update(i, a[i]); } string op; while(cin >> op && op != "End") { if(op == "Query") { int x, y; scanf("%d%d", &x, &y); printf("%d ", getsum(y) - getsum(x - 1)); }else if(op == "Add") { int x, y; scanf("%d%d", &x, &y); update(x, y); }else if(op == "Sub") { int x, y; scanf("%d%d", &x, &y); update(x, -y); } } } }
单点查询,区间更新
解决方法:差分建树!!!!!!!!!!!!
来道裸题
#include <iostream> #include <cstdio> #include<cstdlib> #include<cstring> #include<string> using namespace std; const int MAXN = 500010; int a[MAXN]; int c[MAXN]; int N; int lowbit(int x) { //求x对应的2的k次方(k为x转换为2进制最低位开始连续0的个数) return x & (-x); } void update(int i, int k) {//在i位置加k while(i <= N) { c[i] += k; i += lowbit(i); } } int getsum(int i) {//获得1-i数组元素的和 int res = 0; while(i > 0) { res += c[i]; i -= lowbit(i); } return res; } int main () { int M; scanf("%d%d", &N, &M); for(int i = 1; i <= N; ++i) { scanf("%d", &a[i]); update(i, a[i] - a[i - 1]); } while(M--) { int op; scanf("%d", &op); if(op == 1) { int x, y, k; scanf("%d%d%d", &x, &y, &k); update(x, k); update(y + 1, -k); }else if(op == 2) { int x; scanf("%d", &x); printf("%d ", getsum(x)); } } }
来个最终版
区间更新,区间查询,如何解决????????
维护两个树状数组
#include <iostream> #include <cstdio> #include<cstdlib> #include<cstring> #include<string> using namespace std; typedef long long ll; const int MAXN = 100005; ll a[MAXN]; ll sum1[MAXN]; ll sum2[MAXN]; int N; ll lowbit(ll i) { return i & (-i); } void update(int i, ll k) { ll x = i; while(i <= N) { sum1[i] += k; sum2[i] += k * (x - 1ll); i += lowbit(i); } } ll getsum(int i) { ll ans = 0; ll x = i; while(i > 0) { ans += x * sum1[i] - sum2[i]; i -= lowbit(i); } return ans; } int main () { int Q; scanf("%d%d", &N, &Q); for(int i = 1; i <= N; ++i) { scanf("%lld", &a[i]); update(i, a[i] - a[i - 1]); } // cout << Q << endl; while(Q--) { char op; getchar(); scanf("%c", &op); if(op == 'C') { int a, b; ll c; scanf("%d%d%lld", &a, &b, &c); update(a, c); update(b + 1, -c); }else if(op == 'Q') { int a, b; scanf("%d%d", &a, &b); printf("%lld ", getsum(b) - getsum(a - 1)); } } }