树状数组

说明

树状数组(Binary Indexed Tree) 总结

bin[]为树状数组 n为数组的下标最大值

时间复杂度分析:

  • update O(logn)
  • sum O(logn)

使用方法

  1. memset(bin, 0, sizeof(bin));
  2. n赋值
  3. update(3, 1); 给数组中下标为3的位置更新1
  4. sum(i); 求数组中下标为1~i的值的和

Tips

  • 树状数组无法更新下标为0的数
  • 分清树状数组的操作是更新、修改、取最大/最小值等
  • 用树状数组时经常需要离散化

模版

int bin[maxn],n;
int lowbit(int x){
    return x&(-x);
}
void update(int pos,int val){
    while (pos<maxn) {
        bin[pos]+=val;
        pos+=lowbit(pos);
    }
}
int sum(int pos){
    int ans=0;
    while (pos>0) {
        ans+= bin[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

应用

单点更新区间查和

最一般的应用,每次将树状数组对应位置的值更新。

for (int i=1; i<=n; i++) {
  update(pos[i], val[i]);
}
int ans = sum(r) - sum(l-1);

区间更新单点查询

转化为更新两个点的值来更新区间

update(l,1);
update(r+1,-1);
int val = sum(pos);

求解逆序数

一般需要对序列离散化,可以降低更新和查询的复杂度以及数组大小

for (int i=1; i<=n; i++) {
  update(a[i], 1);
  ans+=i-sum(a[i]);   //插入的数字个数 - 已插入的小于等于a[i]的元素个数
}
printf("逆序数个数为: %d",ans);

区间更新区间查询

使用方法

  1. 给n赋值
  2. memset(c, 0, sizeof(c));
  3. memset(b, 0, sizeof(b));
  4. add(l,r,x);[l,r]区间增加x
  5. sum(l, r); 查询区间[l, r]的和

模版

int n;
const int maxn=500005;
long long c[maxn],b[maxn];
inline int lowbit(int t)
{
    return t&(-t);
}
void update(long long c[],int flag,int x,long long v)
{
    if (flag) for (int i=x; i<=n; i+=lowbit(i)) c[i]+=x*v;
    else for (int i=x; i>0; i-=lowbit(i)) c[i]+=v;
}
long long query(long long c[],int flag,int x)
{
    long long ans=0;
    if (flag) for (int i=x; i>0; i-=lowbit(i)) ans+=c[i];
    else for (int i=x; i<=n; i+=lowbit(i)) ans+=c[i];
    return ans;
}
void add(int l,int r,long long v)
{
    update(b,0,r,v);
    update(c,1,r,v);
    if (l>1)
    {
        update(b,0,l-1,-v);
        update(c,1,l-1,-v);
    }
}
long long sum(int x)
{
    if (x) return query(b,0,x)*x+query(c,1,x-1);
    else return 0;
}
long long sum(int l,int r)
{
    return sum(r)-sum(l-1);
}

results matching ""

    No results matching ""