您的位置: 首页  >  文章  >  浅析树状数组(B.I.T.)(未完待续)

浅析树状数组(B.I.T.)(未完待续)

分类: 文章 • 2023-12-15 16:53:52

浅析树状数组——B.I.T.

beginning

让我们先从这道题开始:P1001 A+B Problem
说明: 我不是在搞笑 !
我们可以探讨一下,用我们所学的知识可以如何解决这道题.

顺序结构 A+B

#include<cstdio>
int a,b;
int main()
{
    scanf("%d%d",&a,&b);
    printf("%d",a+b);
}

明显没有任何毛病…… 傻子才会说有毛病

高精 A+B

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int S(const char *a) { return strlen(a); }
int mx(int a,int b) { return a>b?a:b; }
struct bigint{
    static const int LEN=100001;
    static const int ZR='0';
    int a[LEN];
    bigint() { a[0]=1,a[1]=0; }
    void operator=(char*s) {
        memset(a,0,sizeof(int)*a[0]);
        a[0]=S(s);
        for(int i=0;i<a[0];i++)
            a[a[0]-i]=s[i]-'0';
    }
    void operator=(int s) {
        char t[LEN];
        sprintf(t,"%d",s);
        *this=t;
    }
    bigint(int n) { *this=n; }
    bigint(char *s) { *this=s; }
    void in() {
        char s[LEN];
        scanf("%s",s);
        a[0]=S(s);
        for(int i=0;i<a[0];i++)
            a[a[0]-i]=s[i]-'0';
    }
    void out() {
        for(int i=a[0];i>=1;i--)
            printf("%d",a[i]);
    }
    bigint operator+(const bigint&s) {
        bigint ans;
        ans.a[0]=mx(a[0],s.a[0]);
        int x=0;
        for(int i=1;i<=ans.a[0];i++) {
            ans.a[i]=a[i]+s.a[i]+x;
            x=ans.a[i]/10;
            ans.a[i]%=10;
        }
        while(ans.a[ans.a[0]+1]!=0)ans.a[0]++;
        return ans;
    }
};
bigint a,b,c;
int main() {
    a.in();
    b.in();
    c=a+b;
    c.out();
}

压位高精 A+B

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int S(const char *a) { return strlen(a); }
int mx(int a,int b) { return a>b?a:b; }
struct bigint{
    static const int LEN=101;
    int a[LEN];
    bigint(){}
    void operator=(char*s) {
        memset(a,0,sizeof(a));
        int len=S(s);
        a[0]=len/4;
        if(len%4) a[0]++;
        for(int i=0,j;i<len&&(j=(len-i-1)/4+1);i++)
            a[j]=a[j]*10+s[i]-'0';
    }
    void operator=(int s) {
        char t[LEN];
        sprintf(t,"%d",s);
        *this=t;
    }
    bigint(int n) { *this=n; }
    bigint(char *s) { *this=s; }
    void in() {
        char s[LEN];
        scanf("%s",s);
        *this=s;
    }
    void out() {
        printf("%d",a[a[0]]);
        for(int i=a[0]-1;i>=1;i--)
            printf("%04d",a[i]);
    }
    bigint operator+(const bigint&s) {
        bigint ans=0;
        ans.a[0]=mx(a[0],s.a[0]);
        for(int i=1;i<=ans.a[0];i++) {
            ans.a[i]+=a[i]+s.a[i];
            if(ans.a[i]>=10000)
                ans.a[i]-=10000,ans.a[i+1]++;
        }
        while(ans.a[ans.a[0]+1]!=0)ans.a[0]++;
        return ans;
    }
};
bigint a,b,c;
int main() {
    a.in();
    b.in();
    c=a+b;
    c.out();
}

二分A+B

#include<cstdio>
inline int read()
{
    int a=0; char f=1,c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-f;
        if(c==-1) return -1;
        c=getchar();
    }
    while(c>='0'&&c<='9') a=(a<<1)+(a<<3)+(c^48),c=getchar();
    return a*f;
}
inline int write(int a)
{
    if(a<0) a=(~a)+1;
    if(a/10) write(a/10);
    return putchar(a%10|48);
}
int a=read(),b=read(),l=-2e9,r=2e9;
int main()
{
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(mid<a+b) l=mid;
        else r=mid;
    }
    write(r);
}

或许很多人已经觉得二分A+B已经很神奇了,但是我们今天要学习一种新的做A+B的方法:树状数组(B.I.T).

树状数组简介(不喜欢啰嗦的请直接跳到这里)

树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

经过了如此一番看不懂的说明,或许你会直接绝望掉,But这东西贼重要,而且 这种东西竟然没有STL！！！气不气 QAQ

基础概念

假设数组a[1…n]，那么查询a[1]+…+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。

浅析树状数组(B.I.T.)(未完待续)

来观察这个图：
令这棵树的结点编号为C1，C2…Cn。令每个结点的值为这棵树的值的总和，那么容易发现：

C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

这里有一个有趣的性质：
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。

这样说是不是就要明确一些了?

根据这个性质,就有一个千古大罪人发明了树状数组

代码实现

大体结构

struct B_I_T{
    int C[100001];
    int n;
    ......//函数
};

lowbit

实现

还记得上面说的那一个性质吗?借助C++强大的位运算,我们可以在O(1)时间内求出2^k

int lowbit(int x) { return x - ( x & (x - 1) ); }

浅析树状数组(B.I.T.)(未完待续)

还有一种更简单也更常用的方式,是这样的

int lowbit(int x) { return x & -x; }

浅析树状数组(B.I.T.)(未完待续)

struct B_I_T{
    int C[100001];
    int n;
    inline int lowbit(int x) { return x & -x; }
    ......//函数
};

就可以在结构体中加入这样一个函数了.
不过,更常用的方法不是写在结构体里面,而是写在外面,否则不在结构体当中就只能用B_I_T::lowbit(x) 了,即

inline int lowbit(int x) { return x & -x; }
struct B_I_T{
    int C[100001];
    int n;
    ......//函数
};

作用

update
实现
void update(int x,int val) {//A[x]+=val;
	for(int i=x;i<=n;i+=lowbit(x)) C[x]+=val;
}

这种使用for循环的做法,和下面使用while循环的原理是一样的.

void update(int x,int val) {//A[x]+=val;
	while(x<=n) {
		C[x]+=val;
		x+=lowbit(x);
	}
}

假设n=8,执行update(3,5),则有如下流程

x=3 C[3]+=5 x=3+lowbit(3)=4
x=4 C[4]+=5 x=4+lowbit(4)=8
x=8 C[8]+=5 x=8+lowbit(8)=16
x=16 退出

对照上文的图片 我也不知道有多上文 我们可以知道,每一次C数组中执行加操作的下标,刚好都包括了A[3]!

作用

作用1——初始化

inline void init() {
    scanf("%d",&n);
    for(reg int i=1;i<=n;i++) {
        scanf("%d",&a);
        update(i,a);
    }
}

作用2——改变单点的值 话说就是拿来干这件事的就不讲了
作用3——区间修改 详见洛谷日报

相关推荐