跳转至

树状数组

单点加 区间求和

 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
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 5e5 + 9;
int a[MAXn + 9], t[MAXn + 9];
int n;

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

// O(n)建树法1 - 前缀和
int addi[MAXn + 9];
void build1() {
    for(int i = 1; i <= n; i ++) {
        addi[i] = addi[i-1] + a[i];
        // t[i] = [i-lowbit(i)+1, i]
        t[i] = addi[i] - addi[i - lowbit(i)];
    }
}

// O(n)建树法2 - 每次更新父节点
void build2() {
    for(int i = 1; i <= n; i ++) {
        // t[i] += a[i];
        int fi = i + lowbit(i);
        if(fi <= n) t[fi] += t[i];
    }
}

void add(int x, int v) {
    for(int xi = x; xi <= n; xi += lowbit(xi))
        t[xi] += v;
}

int sum(int x) {
    int ans = 0;
    for(int xi = x; xi >= 1; xi -= lowbit(xi))
        ans += t[xi];
    return ans;
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &t[i]);
        // add(i, a[i]);
    }
    build2();
    int ia, ib, ic;
    for(int io = 1; io <= m; io ++) {
        scanf("%d%d%d", &ia, &ib, &ic);
        if(ia == 1) add(ib, ic);
        else printf("%d\n", sum(ic) - sum(ib - 1));
    }
    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
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 5e5 + 9;
int a[MAXn + 9], cf[MAXn + 9], t[MAXn + 9];
int n;

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

void build() {
    for(int i = 1; i <= n; i ++) {
        t[i] += cf[i];
        int fai = i + lowbit(i);
        if(fai <= n) t[fai] += t[i];
    }
}

void fadd(int x, int v) {
    for(int ix = x; ix <= n; ix += lowbit(ix))
        t[ix] += v;
}

int sum(int x) {
    int ans = 0;
    for(int ix = x; ix >= 1; ix -= lowbit(ix))
        ans += t[ix];
    return ans;
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        cf[i] = a[i] - a[i-1];
        // fadd(i, cf[i]);
    }
    build();
    int op;
    for(int iot = 1; iot <= m; iot ++) {
        scanf("%d", &op);
        if(op == 1) {
            int x, y, v;
            scanf("%d%d%d", &x, &y, &v);
            fadd(x, v);
            fadd(y + 1, -v);
        }
        else {
            int x;
            scanf("%d", &x);
            printf("%d\n", sum(x));
        }
    }
    return 0;
}