有关单点修改，区间查询的两个算法

树状数组

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],tr[N];
int n,m;
int lowbit(int x)
{
    return x & -x;
}
void add(int u,int v)
{
    for(int i = u;i <= n;i += lowbit(i)) tr[i] += v;
}
int query(int u)
{
    int sum = 0;
    for(int i = u;i > 0;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) add(i,a[i]);
    while (m -- )
    {
        int k,x,y;
        cin >> k >> x >> y;
        if(!k) cout << query(y) - query(x - 1) << endl;
        else add(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
59
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node
{
    int l,r;
    int sum;
}tr[4 * N];
int n,m;
int a[N];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u,int l,int r)
{
    if(l == r) tr[u] = {l,r,a[r]};
    else
    {
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int sum = 0;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) sum = query(u << 1,l,r);
    if(r > mid) sum += query(u << 1 | 1,l,r);
    return sum;
}
void modify(int u,int a,int v)
{
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(a <= mid) modify(u << 1,a,v);
        else modify(u << 1 | 1,a,v);
        pushup(u);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while (m -- )
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(!k) printf("%d\n",query(1,x,y));
        else modify(1,x,y);
    }
    return 0;
}

更多请查看: 我的Acwing主页