树状数组-单点查询算法

原题P3374

$lowbit()$将某数在二进制下的高位$1$去掉，只剩最后一个最低位$1$。

例如 $lowbit(3_{10}(101_{2}))=1_{10}(001_{2})$

那么，若有一个数组$a[n]$，它的前缀和的树状数组为$t$

那么

1
2
3
4
5
6
7
while(j<=n){

    t[j]+=a[i];

    j+=lowbit(j);//跳转到需要此值的地方

}

（初始化）

若我们需要$a[i]+a[i+1]+···+a[j]$，

则需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
i--;//因为我们不能舍弃a[i]所以减1

    while(x){//寻找a[1]+a[2]+···+a[i-1]

        x_sum+=t[x];

        x-=lowbit(x);

    }

    while(y){//寻找a[1]+a[2]+···+a[j]

        y_sum+=t[y];

        y-=lowbit(y);

    }

    return y_sum-x_sum;

代码

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
#include<bits/stdc++.h>

int n,m,t[500002];

int lowbit(int k){

    return k&amp;-k;

}

void add(int x,int y){

    while(x&lt;=n){

        t[x]+=y;

        x+=lowbit(x);

    }

    return;

}

int sum(int x,int y){

    int x_sum=0,y_sum=0;

    x--;

    while(x){

        x_sum+=t[x];

        x-=lowbit(x);

    }

    while(y){

        y_sum+=t[y];

        y-=lowbit(y);

    }

    return y_sum-x_sum;

}

int main(){

    scanf(&quot;%d%d&quot;,&amp;n,&amp;m);

    for(int i(1);i&lt;=n;i++){

        int in;

        scanf(&quot;%d&quot;,&amp;in);

        add(i,in);

    }

    for(int i(1);i&lt;=m;i++){

        int c,a,b;

        scanf(&quot;%d%d%d&quot;,&amp;c,&amp;a,&amp;b);

        if(c==1){

            add(a,b);

        }else{

            printf(&quot;%d\n&quot;,sum(a,b));

        }

    }

    return 0;

}
信息 > 算法
树状数组-单点查询算法
https://www.insaua.com/articles/bit-point-query/
作者
Eason3Blue
发布于
2022年8月15日
许可协议