树状数组详解与模版

朴灿烈づ我的快乐病毒、 2021-10-29 12:44 341阅读 0赞

单点更新

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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("*********\n")
    #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\n",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;
    }

![1468777-20190813142702934-385818861.png][]

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;
    }

![1468777-20190813142729248-308897245.png][]

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标记的线段树要优。

![1468777-20190813142822150-942142752.png][]

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;
    }

![1468777-20190813142851962-1123741938.png][]

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;
    }

![1468777-20190813142930913-543375092.png][]

#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('\n');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/smallhester/p/11345721.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/8013e0d4243941e3831328bb2dfad717.png
[1468777-20190813142702934-385818861.png]: /images/20211029/a3af12c948524c2c81e983a663b57477.png
[1468777-20190813142729248-308897245.png]: /images/20211029/836971509da943eebbc6a91c2a4765b7.png
[1468777-20190813142822150-942142752.png]: /images/20211029/4c03142d1b3d4e13888d3fc7d6f6fc36.png
[1468777-20190813142851962-1123741938.png]: /images/20211029/4208b6da61b74a0ca71845c37d2c8031.png
[1468777-20190813142930913-543375092.png]: /images/20211029/a2cbc3f77b304691b83727c671f349b5.png