树状数组(Binary Indexed Tree, BIT)

时间:2024-07-13 09:41:11

树状数组(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;
}

代码实现

#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;
}