树状数组

树状数组

对于区间之间的增删查改，如果单纯按照之前的想法就是O(1)查询，然后O(n)的时间复杂度去进行修改。

而树状数组查询和修改都是O(logn)的复杂度

接下来详细讲一下树状数组的基本操作

数组A（原数组） /// 数组C（树状数组）

原理： 找出每个数的二进制最低位的1，然后其他1归零，剩下的这个二进制数就是C数组元素的个数(也就是求lowbit）可以直接这么求（证明暂省）

luoguP3374

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
int a[maxn];
int c[maxn]={0};
inline int lowbit(int x)
{
    return x&(-x);
}
int query(int x)///区间求和
{
    int sum=0;
    while (x>0)
    {
        sum+=c[x];
        x=x-lowbit(x);
    }
    return sum;
}
void modify(int idx,int math,int k)///修改 k是边界 idx修改地址 math修改值，修改一个节点
{
    while (idx<=k)
    {
        c[idx]+=math;
        idx+=lowbit(idx);
    }

}
int all(int a,int b)///区间查询
{
    return query(b)-query(a-1);
}
int main()
{  
   int n,m,x;
   scanf("%d%d",&n,&m);
   int a,b,c;
   for (int i=1;i<=n;++i)
   {
       scanf("%d",&x);
       modify(i,x,n);
   }
   while (m--)
   {
      scanf("%d%d%d",&a,&b,&c);
      if (a==1)
      {
         modify(b,c,n);
      }
      else if (a==2)
      {
        cout<<all(b,c)<<endl;
      }
   }
  return 0;
}

当然树状数组也支持区间修改和单点查询（一般采用差分数组和前缀和）

此时的C数组就是差分数组////B数组就是树状数组////A数组就是储存数组

luoguP3368

思维转化，区间修改的话不妨弄一个差分数组C，然后C[i]=A[i]-A[i-1]对于修改之后的值在区间[a,b]上增加一个d

只需要对于C[a]+d ///C[b+1]减去一个d即可实现区间修改操作

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
int A[maxn]={0};///储存数组
int B[maxn]={0};///树状数组
int C[maxn]={0};///差分数组
inline int lowbit(int x)
{
    return x&(-x);
}
int query(int x)///和上面的操作一样
{
    int sum=0;
    while (x>0)
    {
        sum+=B[x];
        x=x-lowbit(x);
    }
    return sum;
}
void modify(int idx,int math,int k)
{
    while (idx<=k)
    {
        B[idx]+=math;
        idx+=lowbit(idx);
    }

}

int main()
{  
   int n,m;
   cin>>n>>m;
   int a,b,c,d;
   for (int i=1;i<=n;++i)
   {
       cin>>A[i];
       C[i]=A[i]-A[i-1];
       modify(i,C[i],n);///改动的地方只是把差分数组当作原来的原数组
   }
   while (m--)
   {
      cin>>a;
      if (a==1)
      {  
         cin>>b>>c>>d;
         modify(b,d,n);///转化一下就是两点之间的修改操作
         modify(c+1,-d,n);
      }
      else if (a==2)
      { 
        cin>>b;
        cout<<query(b)<<endl；///从1到b的区间和
      }
   }
  return 0;
}

一般讲来树状数组支持的就是单点查询、区间修改和区间求和、单点查改

其实严格意义上还可以进行树状数组维护区间最值（当然树套树我是不会的啦）//doge

如果每一次都直接遍历一遍max就过于慢速

在原来区间和的基础之上C[i]储存的是A[i-lowbit(i)+1]一直到A[i]之间的数值，区间最值问题当然不能简单的这样区域合并

C[i]此时应该储存的是C[i-lowbit+1]到C[i]之间的最大值

观察下之前的区间加法图，譬如我现在选择C[4]接下来我就直接将A[4]的值赋值给C[4],然后再直接与C[3],C[2]进行比较

不难发现，C[i]只与C[i-2^x]存在关系

void modify(int idx,int math,int k)///修改 k是边界 idx修改地址 math修改值
{
    while (idx<=k)
    {
        c[idx]=math;///该区域肯定要包括自己，所以首先把自己加入进去
        for (int i=1;i<lowbit(idx);i<<=1)///直接枚举
            c[idx]=max(c[idx],c[idx-i]);
        idx+=lowbit(idx);
    }
}

对于区间查询就只需要找出区间覆盖子段

1.第一种情况就是区间[x,y]包含[y-lowbit(y),y],即

y-lowbit(y)>x,此种状态下就直接枚举区间比较区间最大值

2.不包括的情况，只能将y-1，

用原来的a[y]去进行比较

int query(int x，int y)///求区间最大值
{
    if(x==y)return a[x];///最后区间只有一个数那就是最大值
    if(y-lowbit(y)>x)return max(c[y],query(x,y-lowbit(y)));
    else return max(a[y],query(x,y-1));
}

参考博客1
参考博客2

树状数组

原文：https://www.cnblogs.com/qimang-311/p/13380293.html