树状数组（Binary Indexed Tree, BIT）

树状数组（Binary Indexed Tree, BIT）

树状数组（Binary Indexed Tree, BIT），也称为 Fenwick Tree，是一种用于高效处理数组前缀和查询和单点更新的数据结构。它能够在 (O(\log n)) 时间内完成单点更新和前缀和查询操作。

基本概念

1. 前缀和：给定一个数组 a，前缀和 prefix_sum[i] 表示 a[0] + a[1] + ... + a[i]。
2. 单点更新：更新数组 a 中的某个元素 a[i]。

树状数组的结构

树状数组通过一种特殊的方式组织数组元素，使得前缀和查询和单点更新都能高效进行。具体来说，树状数组 bit 是一个与原数组 a 大小相同的数组，但它的每个元素 bit[i] 存储的是原数组 a 中某些元素的和。

树状数组的构建

1. 更新操作：

   • 更新 a[i] 时，需要更新 bit 中所有包含 a[i] 的元素。
   • 具体操作是：从 i 开始，不断将 i 加上其最低位的 1，直到超出数组范围。

2. 查询操作：

   • 查询 a[0] + a[1] + ... + a[i] 时，需要累加 bit 中某些元素的值。
   • 具体操作是：从 i 开始，不断将 i 减去其最低位的 1，直到 i 变为 0。

lowbit 原理

lowbit 是一个在树状数组（Binary Indexed Tree, BIT）中常用的操作，用于获取一个整数的二进制表示中最低位的 1 及其后面的 0 所构成的数值。具体来说，lowbit(x) 返回的是 x 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。

原理

lowbit 的原理基于补码表示法。对于一个正整数 x，其 lowbit 可以通过以下公式计算：

[ \text{lowbit}(x) = x & (-x) ]

这里的 & 表示按位与操作。

解释

1. 补码表示：

   • 在计算机中，负数通常以补码形式存储。对于一个正整数 x，其负数 -x 的补码表示是 x 的二进制表示按位取反后加 1。

2. 按位与操作：

   • 按位与操作 & 会将两个数的二进制表示中对应位都为 1 的位保留，其他位变为 0。

3. 计算 lowbit：

   • 对于一个正整数 x，其补码表示 -x 的二进制形式中，最低位的 1 及其后面的 0 会与 x 的二进制形式中相同位置的 1 对应。
   • 因此，x & (-x) 的结果就是 x 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。

示例

假设 x = 6，其二进制表示为 0110：

1. x 的补码表示 -x 是 -6，其二进制表示为 1010（按位取反后加 1）。
2. 进行按位与操作：
   • 0110 (6)
   • 1010 (-6)
   • 0010 (2)

因此，lowbit(6) 的结果是 2。

以下是一个简单的 lowbit 函数实现：

int lowbit(int x) {
    return x & -x;
}
1
2
3

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+100,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m;
int a[N];
int c[N];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)
{
    int s=0;
    for(;x>0;x-=lowbit(x))
    {
        s+=c[x];
    }
    return s;
}
void modify(int id,int x)
{
    for(;id<=n;id+=lowbit(id))
    {
        c[id]+=x;
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],modify(i,a[i]);
    while(m--)
    {
        int id,x,y;
        cin>>id>>x>>y;
        if(id==1) modify(x,y);
        else cout<<query(y)-query(x-1)<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    T=1;
    //cin>>T;
    while(T--)
     {
         solve();
     }
     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