算法与数据结构---树状数组_二维树状数组区间查询区间修改

作者：繁依Fanyi0 | 2024-05-31 20:16:19

踩

二维树状数组区间查询区间修改

树状数组

树状数组例题

#130. 树状数组 1 ：单点修改，区间查询 - 题目 - LibreOJ (loj.ac)

#131. 树状数组 2 ：区间修改，单点查询 - 题目 - LibreOJ (loj.ac)

#132. 树状数组 3 ：区间修改，区间查询 - 题目 - LibreOJ (loj.ac)

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P5367 【模板】康托展开 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Permutation - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#133. 二维树状数组 1：单点修改，区间查询 - 题目 - LibreOJ (loj.ac)

#134. 二维树状数组 2：区间修改，单点查询 - 题目 - LibreOJ (loj.ac)

#135. 二维树状数组 3：区间修改，区间查询 - 题目 - LibreOJ (loj.ac)

P3810 【模板】三维偏序（陌上花开） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

所有资料

树状数组（BIT）—— 一篇就够了 - Last_Whisper - 博客园 (cnblogs.com)

树状数组 - OI Wiki (oi-wiki.org)

算法学习笔记(20): 二维偏序 - 知乎 (zhihu.com)

[https://blog.csdn.net/wbin233/article/details/72998375

高级树状数组——区间修改区间查询、二维树状数组 - 胡小兔 - 博客园 (cnblogs.com)

# 【模板】树状数组 1—区间修改，单个添加

题目描述

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 $x$
求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n, m$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

1 x k 含义：将第 $x$ 个数加上 $k$
2 x y 含义：输出区间 $[x, y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 $30\%$ 的数据， $\le n \le 8$ ， $1\le m \le 10$ ；
对于 $70\%$ 的数据， $1\le n,m \le 10^4$ ；
对于 $100\%$ 的数据， $1\le n,m \le 5\times 10^5$ 。

数据保证对于任意时刻， $a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $2^{31}, 2^{31})$ 范围内。

样例说明：

故输出结果14、16

代码

#include<bits/stdc++.h>
#include<algorithm> 
#define ll long long
using namespace std;
#define MAXN 1000001

ll a[MAXN],f[MAXN<<2]/*区间和*/,n,m;

inline void build(ll k,ll l,ll r){//当前这个点标号为k
	 if( l == r ){
	 	f[k] = a[l];//走到底了，直接赋值
		 return ; 
	 } 
	 ll mid = (l+r)>>1;
	 build(k+k,l,mid);
	 build(k+k+1,mid+1,r);
	 f[k] = f[k+k] /*l到mid的和*/+f[k+k+1]/*mid+1 到 r的和*/;
}
inline void add(ll k,ll l,ll r,ll x,ll y){
	//当前要在下标为k的点，对应区间【l，r】，在里面 下标为x的地方加上y 
	f[k] += y;//【l，r】区间一定包含x，x要+y，那【l，r】区间上的和（即f【k】）也要+y 
	if(l == r){
		return;//到底了 
	} 
	ll mid = (l+r)>>1;
	if(x <= mid) add(k+k,l,mid,x,y);//左边递归 
	else add(k+k+1,mid+1,r,x,y);//否则右边递归 
}
ll sum(ll k,ll l,ll r,ll s,ll t){
	//下标为k的点 代表区间【l，r】，求区间【s，t】的和 
	if( l == s && r == t) return f[k];//区间完全重合
	ll mid = (l+r)>>1;
	if(t <= mid) 
	   return sum(k+k,l,mid,s,t);//完全在左边 
	else if(s>mid) 
	   return sum(k+k+1,mid+1,r,s,t);//完全在右边
	else 
	    return sum(k+k,l,mid,s,mid) + sum(k+k+1,mid+1,r,mid+1,t);//横跨两个区间 
} 

int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++){
	    scanf("%lld",&a[i]);
	}
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll t,x,y;
		scanf("%lld%lld%lld",&t,&x,&y);
		if(t==1){
			add(1,1,n,x,y);
		}
		else printf("%lld\n",sum(1,1,n,x,y));
	}
	return 0;
}

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

#130. 树状数组 1 ：单点修改，区间查询 - 题目 - LibreOJ (loj.ac)

#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 1e6 + 10;

int tr[N];

int lowbits(int x) {
    return x & (-x);
}

void updata(int id, int x) {//更新
    for (int i = id; i < N; i += lowbits(i)) {
        tr[i] += x;
    }
}

int query(int x) {//区间查询
    int ans = 0;

    for (int i = x; i; i -= lowbits(i)) {
        ans += tr[i];
    }

    return ans;
}

signed main(void) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        updata(i, x);
    }

    while (q --) {
        int opt;
        cin >> opt;

        if (opt == 1) {
            int id, x;
            cin >> id >> x;
            updata(id, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(r) - query(l - 1) << endl;
        }
    }
}
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

#131. 树状数组 2 ：区间修改，单点查询 - 题目 - LibreOJ (loj.ac)

#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 1e6 + 10;

int tr[N];

int lowbits(int x) {
    return x & (-x);
}

void updata(int id, int x) {
    for (int i = id; i < N; i += lowbits(i)) {
        tr[i] += x;
    }
}

int query(int x) {
    int ans = 0;

    for (int i = x; i; i -= lowbits(i)) {
        ans += tr[i];
    }

    return ans;
}

signed main(void) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    while (q --) {
        int opt;
        cin >> opt;

        if (opt == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            updata(l, x);
            updata(r + 1, -x);
        } else {
            int id;
            cin >> id;
            cout << query(id) + a[id] << endl;
        }
    }
}
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

#132. 树状数组 3 ：区间修改，区间查询 - 题目 - LibreOJ (loj.ac)

#include <bits/stdc++.h>
#define int long long int
using namespace std;

const int N = 1e6 + 10;

int tr[N], tri[N];

int lowbits(int x) {
    return x & (-x);
}

void updata(int tr[], int id, int x) {
    for (int i = id; i < N; i += lowbits(i)) {
        tr[i] += x;
    }
}

int query(int tr[], int x) {
    int ans = 0;

    for (int i = x; i; i -= lowbits(i)) {
        ans += tr[i];
    }

    return ans;
}

int get(int x) {
    return (x + 1) * query(tr, x) - query(tri, x);
};

signed main(void) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i ++)
        tr[i] = a[i] - a[i - 1], tri[i] = tr[i] * i;

    for (int x = 1; x <= n; x ++)
        for (int i = x - 1; i >= x - lowbits(x) + 1; i -= lowbits(i))
            tr[x] += tr[i], tri[x] += tri[i];

    while (q --) {
        int opt;
        cin >> opt;

        if (opt == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            updata(tr, l, x);
            updata(tr, r + 1, -x);
            updata(tri, l, l * x);
            updata(tri, r + 1, (r + 1) * (-x));
        } else {
            int l, r;
            cin >> l >> r;
            cout << get(r) - get(l - 1) << endl;
        }
    }
}
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

P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#define int long long int
#define all(x) x.begin(), x.end()
#define c1() cout << " ----------------------------- \n";
#define c2() cout << " +++++++++++++++++++++++++++++ \n";
#define cr(x) cout << "[ " << #x << " = " << x << " ]\n";
#define ct(x, y) cout << "[ " << #x << " = " << x << ", " << #y << " = " << y << " ]\n";
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 1e6 + 10;

int tr[N];

int lowbits(int x)
{
    return x & (-x);
}

void upata(int x)
{
    for(int i = x; i < N; i += lowbits(i))
        tr[i] ++;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbits(i))
        res += tr[i];
    return res;
}

signed main()
{
    IOS;

    int n;
    cin >> n;
    vector<int> a(n + 1), b;
    for(int i = 1; i <= n; i ++)
        cin >> a[i], b.push_back(a[i]);
    
    sort(all(b));
    b.erase(unique(all(b)), b.end());

    int ans = 0;
    // cout << b.size() << endl;
    // cout << a[1] << endl;
    for(int i = 1; i <= n; i ++)
    {
        int x = lower_bound(all(b), a[i]) - b.begin() + 1;
        ans += query(N - 1) - query(x);
        upata(x); 
    }
    cout << ans << endl;
}
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

P5367 【模板】康托展开 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, mod = 998244353;

typedef long long LL;

int tr[N];
int f[N], a[N];

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

void add(int x, int k)
{
    for(int i = x; i <= N; i += lowbit(i))
        tr[i] += k;
}

int query(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) 
        sum += tr[i];
    return sum;
}

void init()
{
    f[0] = 1;
    for(int i = 1; i <= N; i ++)
        f[i] = 1LL * f[i - 1] * i % mod, add(i, 1);
}

int main()
{
    init();
    int n;
    cin >> n;
    
    LL ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i]; 
        ans += 1LL * (query(a[i] - 1)) * f[n - i] % mod;
        ans %= mod;
        add(a[i], -1);
    } 
    cout << (ans + 1) << endl;
    return 0;
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/654197