树状数组

时间复杂度

• 单点修改 O(logn)
• 区间查询 O(logn)

前置知识

lowbit()运算：非负整数x在二进制表示下最低位1及其后面的0构成的数值。

#define lowbit(x) x & -x

树状数组的思想

树状数组的本质思想是使用树结构维护”前缀和”，从而把时间复杂度降为O(logn)。

1. 每个结点t[x]保存以x为根的子树中叶结点值的和

   \[t[x]=a[x]+t[x-1]+t[x-1-lobit(x-1)]+...... \]

2. 每个结点覆盖的长度为lowbit(x)

3. t[x]结点的父结点为t[x + lowbit(x)]

4. 树的深度为log2n+1

树状数组的操作

add

• add(x, k)表示将序列中第x个数加上k。

  

void add(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}

ask

• ask(x)表示将查询序列前x个数的和

int ask(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i))
        sum += t[i];
    return sum;
}

树状数组的扩展

一：

• 修改区间和

• 查询元素

  方法：构造tr为a的差分数组。

  则修改a区间[l,r]和<=>修改tr,tr[l]+c,tr[r+1]-c

  则查询a[x]元素 <=> 求tr的1~x的前缀和

  模板题

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int N = 1e5 + 10;
  int a[N];
  LL tr[N];
  int n,m;
  
  #define lowbit(x) x&(-x)
  
  void add(int x,int c)
  {
      for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
  }
  
  LL sum(int x)
  {
      LL res = 0;
      for(int i = x;i;i-=lowbit(i)) res+=tr[i];
      return res;
  }
  int main()
  {
      scanf("%d%d", &n, &m);
      for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      
      for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);
      
      while (m -- )
      {
          char op[2];
          int l,r,d;
          scanf("%s%d",op,&l);
          if(op[0]==‘C‘)
          {
              scanf("%d%d",&r,&d);
              add(l,d),add(r+1,-d);
          }
          else printf("%d\n",sum(l));
      }
      return 0;
  }
  

二：

• 修改区间和

• 查询区间和

  

  因此，我们维护两个树状数组

  模板题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n,m;
int a[N];
LL tr1[N],tr2[N];
#define lowbit(x) x&(-x)

void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL sum(LL tr[],int x)
{
    LL res = 0;
    for(int i = x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

LL ps(int x)
{
    return sum(tr1,x)*(x+1) - sum(tr2,x);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) 
    {
        LL b = a[i] - a[i-1];
        add(tr1,i,b),add(tr2,i,b*i);
    }
    
    while (m -- ){
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]==‘C‘)
        {
            scanf("%d",&d);
            add(tr1,l,d),add(tr1,r+1,-d);
            add(tr2,l,d*l),add(tr2,r+1,(r+1)*-d);
        }
        else printf("%lld\n",ps(r)-ps(l-1));
    }
    return 0;
}

树状数组小结