树状数组小结

时间:2021-08-23 22:57:46   收藏:0   阅读:27

树状数组

时间复杂度

前置知识

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
void add(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}
ask

技术分享图片

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

树状数组的扩展

一:
二:
#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;
}

原文:https://www.cnblogs.com/aitejiu/p/15177662.html

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!