目录

lowbit

树状数组1

树状数组2

逆序对

树状数组二分

二维树状数组

---

lowbit

得到x的二进制数的最后一位

int lowbit(int x){
    return x & -x
}

设数组数组为 c[ ]

 

树状数组1

• 单点修改
• 区间查询

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 2e5+5;
int a[N], n, q;
ll c[N];
inline int lowbit(int x){
    return x & -x;
}
inline void modify(int x, int d){
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
inline ll query(int x){
    ll res = 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &a[i]);
        modify(i, a[i]);
    }
    while(q--) {
        int ty; scanf("%d", &ty);
        if(ty == 1) {
            int x, d; scanf("%d %d", &x, &d);
            modify(x, d - a[x]);
            a[x] = d;
        }else {
            int x; scanf("%d", &x);
            printf("%lld\n", query(x));
        }
    }
 
    return 0;
}

 

树状数组2

• 区间修改
• 区间查询

 这里的mod 2的64次方等价于无符号long long的自然溢出。

这里配合差分的思想，并且要开两个树状数组来维护。一个维护 d[i]    一个维护  i * d[i]

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
typedef unsigned long long u64;
 
const int N = 2e5+5;
int n, q;
 
inline int lowbit(int x){
    return x & -x;
}
template<class T>
struct BIT{
    T c[N];
    int size;
    void resize(int n){size = n;}
    inline void modify(int x, T d){
        while(x <= size){
            c[x] += d;
            x += lowbit(x);
        }
    }
    inline T query(int x){
        T res = 0;
        while(x){
            res += c[x];
            x -= lowbit(x);
        }
        return res;
    }
};
BIT c1, c2;
int main(){
    scanf("%d %d", &n, &q);
    c1.resize(n);
    c2.resize(n);
    while(q--) {
        int ty; scanf("%d", &ty);
        if(ty == 1) {
            int l, r;
            u64 d; 
            scanf("%d %d %llu", &l, &r, &d);
            c1.modify(l, d);
            c1.modify(r + 1, -d);
            c2.modify(l, l * d);
            c2.modify(r + 1, (r + 1) * (-d));
 
        }else {
            int x; scanf("%d", &x);
            printf("%llu\n", (x + 1) * c1.query(x) - c2.query(x));
        }
    }
 
    return 0;
}

 

逆序对

 用树状数组求解逆序对还是很巧妙的，怎么说的，本身树状数组就是一个很巧妙的东西。

• 静态转动态的思想
• hash   （权重）

problem：记得开ll，要不然结果会溢出。

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
int n;
ll c[100005];
inline int lowbit(int x){
    return x & -x;
}
inline void modify(int x, int d){
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
inline ll query(int x){
    int res = 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main(){
    scanf("%d", &n);
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        int x; scanf("%d", &x);
        x = n + 1 - x;
        ans += query(x);
        modify(x, 1);
    }
    printf("%lld\n", ans);
    return 0;
}

树状数组二分

 problem：

        树状数组上二分，比较直观的一种理解就是对T进行二分，容易看出时间复杂度为     O(n logn logn) 

        但有一种更加高效的算法，可以使得时间复杂度压缩至O(nlogn)

 树状数组c[i] 存的是一段区间的值，这段区间的起点和长度由i来决定，确切地说，由i的二进制来确定。

所以我们的S就可以由一段一段的区间分割开来。j从大到小遍历，是表明从大区间到小区间收缩。最终S由若干个区间组成。

注意，j是可以取到0的，   2的0次方等于1     

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 2E5 + 5;
ll c[N], a[N];
int n, q;
inline int lowbit(int x){
    return x & -x;
}
inline void modify(int x, ll d){
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
inline int query(ll s){
    int pos = 0;
    for(int j = 18; j >= 0; --j)
        if(pos + (1 << j) <= n && c[pos + (1 << j)] <= s){
            pos += (1 << j);
            s -= c[pos];
        }
    return pos;
}
int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &a[i]);
        modify(i, a[i]);
    }
    while(q--) {
        int ty; scanf("%d", &ty);
        if(ty == 1){
            int x;
            ll d;
            scanf("%d %lld", &x, &d);
            modify(x, d - a[x]);
            a[x] = d;
        }else {
            ll s; scanf("%lld", &s);
            printf("%d\n", query(s));
        }
    }   
 
    return 0;
}

二维树状数组

 

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
int n, m, q;
int a[505][505];
ll c[505][505];
inline int lowbit(int x){
    return x & -x;
}
 
void modify(int x, int y, ll d){
    for(int p = x; p <= n; p += lowbit(p))
        for(int q = y; q <= m; q += lowbit(q))
            c[p][q] += d;
}
 
ll query(int x, int y){
    ll res = 0;
    for(int p = x; p; p -= lowbit(p))
        for(int q = y; q; q -= lowbit(q))
            res += c[p][q];
    return res;
}
 
int main() {
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            scanf("%lld", &a[i][j]);
            modify(i, j, a[i][j]);
        }
    while(q--) {
        int ty; scanf("%d", &ty);
        if(ty == 1) {
            int x, y;
            ll d; 
            scanf("%d %d %lld", &x, &y, &d);
            modify(x, y, d - a[x][y]);
            a[x][y] = d;
        } else {
            int x, y; scanf("%d %d", &x, &y);
            printf("%lld\n", query(x, y));
        }
    }
 
    return 0;
}