树状数组

树状数组的学习可以看b站董晓算法的讲解（极力推荐）。

董老师树状数组博客

oiwiki

大概的思路

img

image-20241106132419398

image-20241106121133413

无论是往点修往后跳还是求前缀和往前跳都是一次跳2^k^，k为x二进制最低有效位。

image-20241106121234276

代码模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找到x最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 区间查询
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){// 查找第一个满足条件的下标（前缀和
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){// 查找最后一个满足条件的下标（前缀和）
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;

点修+区查

P3374 【模板】树状数组 1

https://www.luogu.com.cn/problem/P3374

点修+区查是操作最简单的，直接用要维持的数据来建树，然后单点修改的话就直接对这个点进行modify，区间查询的话就对这个区间query(l,r)；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找一个数的最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 查询前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 查询区间和
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    BIT bit(n);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        bit.modify(i,x);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            bit.modify(x,y);
        }
        else
        {
            cout<<bit.query(x,y)<<'\n';
        }
    }    

    return 0;    
}

区修+点查

树状数组初始值都为0，这是一个差分数组，如果对[l,r]加上某一个数，就modify(l,k)，modify(r+1,-k)，然后如果要点查的话就直接用a[x]+bit.query(x)就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){
        return x & -x;
    }
 
    void modify(int x, T c){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    BIT bit(n+1);
    for(int i=1;i<=m;i++)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            int y,k;
            cin>>y>>k;
            bit.modify(x,k);
            bit.modify(y+1,-k);
        }
        else 
        {
            cout<<a[x]+bit.query(x)<<'\n';
        }
    }

    return 0;    
}

区修+区查

这个是最难的。

image-20241106121902333

P3372 【模板】线段树 1

这一道题的区修就是区间加，区查就是区间和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找到x最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 区间查询
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){// 查找第一个满足条件的下标（前缀和
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){// 查找最后一个满足条件的下标（前缀和）
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    BIT d1(n),d2(n);
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];    
    for(int i=1;i<=n;i++)
    {
        d1.modify(i,a[i]);
        d1.modify(i+1,-a[i]);
        d2.modify(i,i*a[i]);
        d2.modify(i+1,-(i+1)*a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            int k;
            cin>>k;
            d1.modify(x,k);
            d1.modify(y+1,-k);
            d2.modify(x,k*x);
            d2.modify(y+1,-k*(y+1));
        }
        else
        {
            cout<<(y+1ll)*d1.query(y)-1ll*x*d1.query(x-1)-(d2.query(y)-d2.query(x-1))<<'\n';
        }
    }
    return 0;    
}

二维偏序(逆序对)

P1908 逆序对

https://www.luogu.com.cn/problem/P1908

第一种方法是归并排序，第二种方法是树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>ans(n+1);
    ll cnt=0;
    auto msort=[&](auto self,int l,int r)->void{
        if(l==r)return;
        int mid=(l+r)/2;    
        int k=l;
        int i=l,j=mid+1;
        self(self,l,mid);self(self,mid+1,r);
        while(i<=mid&&j<=r)
        {
            if(a[i]<=a[j])ans[k++]=a[i++];
            else ans[k++]=a[j++],cnt+=mid-i+1;
        }
        while(i<=mid)ans[k++]=a[i++];
        while(j<=r)ans[k++]=a[j++];
        for(int i=l;i<=r;i++)a[i]=ans[i];

    };
    msort(msort,1,n);    
    cout<<cnt<<'\n';
    return 0;    
}

树状数组的思路就是先预处理出数组中每一个元素在数组中的大小级别，维护一个存大小级别的树状数组，然后遍历整个数组，将每一个元素的级别依次放入树状数组，根据然后用ans+=i+bit.query(mp[b[i]]);就能直接算出对每一个元素来说的逆序对个数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
 
    Fenwick(int n) : n(n), tr(n + 1, 0){}
 
    int lowbit(int x){// 找到x最低有效位
        return x & -x;
    }
 
    void modify(int x, T c){// 点修
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
 
    void modify(int l, int r, T c){// 区修
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
 
    T query(int x){// 前缀和
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
 
    T query(int l, int r){// 区间查询
        return query(r) - query(l - 1);
    }
 
    int find_first(T sum){// 查找第一个前缀和大于或等于 sum 的下标
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
 
    int find_last(T sum){// 查找最后一个前缀和小于或等于 sum 的下标
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
 
};
using BIT = Fenwick<int>;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];    
    vector<int>p(n+1);
    iota(p.begin(),p.end(),0);
    sort(p.begin()+1,p.end(),[&](int i,int j){
        if(a[i]!=a[j])return a[i]>a[j];//第一个p[i]为b[i]中最大元素的下标
        return i>j;如果两个一样大，那么这个下标大的靠前，这样后面使用bit.query时相同大小的不会相互影响。
    });
    BIT bit(n);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=bit.query(p[i]);
        bit.modify(p[i],1);
    }
    cout<<ans<<'\n';
    return 0;    
}

·