单点更新
void update(int x,int y,int n){ for(int i=x;i<=n;i+=lowbit(i)) //x为更新的位置,y为加的数,n为数组最大值 c[i] += y; }
区间查询（1 - x）
int getsum(int x){ int ans = 0; for(int i=x;i;i-=lowbit(i)) ans += c[i]; return ans; }
高级操作
求逆序对
对于数组a，我们将其离散化处理为b[].区间查询与单点修改代码如下
int lowbit(int x) { return x & (-x); } void update(int p) { while (p <= n) { c[p] ++; p += lowbit(p); } } int getsum(int p) { int res = 0; while(p) { res += c[p]; p -= lowbit(p); } return res; }
a的逆序对个数为：
for(int i = 1; i <= n; i++) { update(b[i]); res += (i - getsum(b[i])); }
poj 2299
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<list> #include<math.h> #include<vector> #include<stack> #include<string> #include<cstring> #include<string.h> using namespace std; typedef long long LL; #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl const int MAXN = 5e5 + 10; const double eps = 1e-8; int c[MAXN]; int n; int a[MAXN],b[MAXN]; int lowbit(int x) { return x & (-x); } void update(int p) { while (p <= n) { c[p] ++; p += lowbit(p); } } int getsum(int p) { int res = 0; while(p) { res += c[p]; p -= lowbit(p); } return res; } int main() { while (~scanf("%d", &n) && n) { memset(c,0,sizeof c); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(a + 1, a + 1 + n); int cnt = unique(a + 1, a + 1 + n) - a - 1; for (int i = 1; i <= n; i++) b[i] = lower_bound(a + 1, a + 1 + cnt, b[i]) - a; LL res = 0; for(int i = 1; i <= n; i++) { update(b[i]); res += (i - getsum(b[i])); } printf("%lld ",res); } }
res就是逆序对个数，ask，需注意b[i]应该大于0
求区间最大值
void Update(int i,int v) { while(i<=maxY) { t[i] = max(t[i],v); i += lowbit(i); } }
int query(int i) { int ans = 0; while(i) { ans = max(ans,t[i]); i -= lowbit(i); } return ans; }
int lowbit(int x) { return x & -x; } void add(int p,int x) { //这个函数用来在树状数组中直接修改 while(p <= n) { c[p] += x; p += lowbit(p); } } void range_add(int l,int r,int x) { //给区间[l, r]加上x add(l,x); add(r + 1, -x); } int ask(int p) { //单点查询前缀和 int res = 0; while(p) { res += c[p]; p -= lowbit(p); } return res; }
void add(ll p, ll x){ for(int i = p; i <= n; i += i & -i) sum1[i] += x, sum2[i] += x * p; } void range_add(ll l, ll r, ll x){ add(l, x), add(r + 1, -x); } ll ask(ll p){ ll res = 0; for(int i = p; i; i -= i & -i) res += (p + 1) * sum1[i] - sum2[i]; return res; } ll range_ask(ll l, ll r){ return ask(r) - ask(l - 1); }
用这个做区间修改区间求和的题，无论是时间上还是空间上都比带lazy标记的线段树要优。
void add(int x, int y, int z){ //将点(x, y)加上z int memo_y = y; while(x <= n){ y = memo_y; while(y <= n) tree[x][y] += z, y += y & -y; x += x & -x; } } int ask(int x, int y){//求左上角为(1,1)右下角为(x,y) 的矩阵和 int res = 0, memo_y = y; while(x){ y = memo_y; while(y) res += tree[x][y], y -= y & -y; x -= x & -x; } return res; }
void add(int x, int y, int z){ int memo_y = y; while(x <= n){ y = memo_y; while(y <= n) tree[x][y] += z, y += y & -y; x += x & -x; } } void range_add(int xa, int ya, int xb, int yb, int z){ add(xa, ya, z); add(xa, yb + 1, -z); add(xb + 1, ya, -z); add(xb + 1, yb + 1, z); } int ask(int x, int y){ int res = 0, memo_y = y; while(x){ y = memo_y; while(y) res += tree[x][y], y -= y & -y; x -= x & -x; } return res; }
#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; ll read(){ char c; bool op = 0; while((c = getchar()) < '0' || c > '9') if(c == '-') op = 1; ll res = c - '0'; while((c = getchar()) >= '0' && c <= '9') res = res * 10 + c - '0'; return op ? -res : res; } const int N = 205; ll n, m, Q; ll t1[N][N], t2[N][N], t3[N][N], t4[N][N]; void add(ll x, ll y, ll z){ for(int X = x; X <= n; X += X & -X) for(int Y = y; Y <= m; Y += Y & -Y){ t1[X][Y] += z; t2[X][Y] += z * x; t3[X][Y] += z * y; t4[X][Y] += z * x * y; } } void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形 add(xa, ya, z); add(xa, yb + 1, -z); add(xb + 1, ya, -z); add(xb + 1, yb + 1, z); } ll ask(ll x, ll y){ ll res = 0; for(int i = x; i; i -= i & -i) for(int j = y; j; j -= j & -j) res += (x + 1) * (y + 1) * t1[i][j] - (y + 1) * t2[i][j] - (x + 1) * t3[i][j] + t4[i][j]; return res; } ll range_ask(ll xa, ll ya, ll xb, ll yb){ return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1); } int main(){ n = read(), m = read(), Q = read(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ ll z = read(); range_add(i, j, i, j, z); } } while(Q--){ ll ya = read(), xa = read(), yb = read(), xb = read(), z = read(), a = read(); if(range_ask(xa, ya, xb, yb) < z * (xb - xa + 1) * (yb - ya + 1)) range_add(xa, ya, xb, yb, a); } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) printf("%lld ", range_ask(i, j, i, j)); putchar(' '); } return 0; }