【算法】树状数组

前言

众所周知，通过前缀和，我们可以很快的在一个很大的数组中求出区间和，但是如果想要去修改数组中的一个数的值，前缀和就无法实现。所以来学习一个新的数据结构：树状数组
（文章中关于树状数组的截图来自于b站视频BV1ce411u7qP）

树状数组

当我们想求出一个数组中起始位置和下标i之间的所有元素和，需要从头开始遍历到下标i。但是这样的效率特别低，所以就有如下思考：把相邻数字两两求和后存在一个新数组中，这样遍历的时候会节省一半的时间，但是在求和的时候仍然要遍历很多的数据，效率仍然很低。不如多加几层，直到新开的数组中只有一个元素为止。这样即使要求和的数字很多，也只需要利用这些额外的数组来计算出需要的答案。如下图所示，从下到上，第一层是原始数组，第二层是原始数组中每相邻两个数合成后得到的数组，第三层是原始数组中每相邻四个数合成后得到的数组。如果要计算出前15个数字，那么只需要计算4个数，大大加快计算速度
但是会发现，在这些数中，有一些数字是用不到的，如果去掉这些数字后，保留下来的有用的数字恰好和原始数组的长度相同。
请看下图：

将这个树形结构中的数从左到右放进一个新的数组中，这个数组就是树状数组。每一个元素的下标就是合成这个数的数中，在原始数组中最右侧的那个数的下标。假设下标是从1开始的。我们已知树状数组中的一个数的下标，要怎么得知这个数是由原数组中多少个数合成的呢？
lowbit函数就能实现
代码如下

def lowbit(x):
    return x&(-x)

这个函数很简单，只有一条语句，通过这样的计算可以很高效的求出一个数在二进制下，最右边的1的权是多少。
通过观察发现，树状数组中的下标为i的元素恰好是由原始数据中连续的lowbit(i)个数合成的。而放在树中，同一层元素的lowbit()都是相同的，他上一层元素的lowbit()恰好是这层的两倍。
直到这个规律之后我们就能做以下的操作了

计算前m个元素的和

我们知道了所求区间最右侧lowbit(m)个元素之和存在树状数组下标m的位置，还剩下长度为m-lowbit(m)的区间，也一样可以在树状数组中找出他最右侧的lowbit(m-lowbit(m))个元素和，没错，只要通过递归或循环就能计算出结果了

增减下标i的元素的值

访问下标i的位置，然后对其进行增减操作，这步操作后，会影响到树状数组中在其上层的元素，所以需要接着不断加上lowbit(i)然后找到他上层的元素进行修改。树状数组的初始化其实就是开辟一个空的数组，自定义一个add()函数可以对下标i的元素进行增加，然后从前往后遍历不断的执行add()函数即可。

例题P3374 【模板】树状数组 1

代码实现

python

def lowbit(x):
    return x&(-x)
def add(x, n, k):#x为树状数组的编号，n为数组大小，k为要加的值
    while x<=n:
        f[x]+=k
        x+=lowbit(x)
def ask(x):
    if x==0:
        return 0
    return ask(x-lowbit(x))+f[x]
# 循环版本
# def ask(x):
#     res=0
#     while x>0:
#         res+=f[x]
#         x-=lowbit(x)
#     return res
n,m=map(int, input().split())
a=list(map(int, input().split()))
f=[0]*(n+1)
for i in range(1,n+1):
    add(i, n, a[i-1])
while m>0:
    op,x,y=map(int, input().split())
    if op==1:
        add(x, n, y)
    else:
        print(ask(y)-ask(x-1))
    m-=1

c++

#include<bits/stdc++.h>
using namespace std;
int n,m,tree[2000010];
int lowbit(int k)
{
    return k & -k;
}
void add(int x,int k)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
            add(b,c);
        if(a==2)
            cout<<sum(c)-sum(b-1)<<endl;
    }
}

原文地址：https://blog.csdn.net/qq_59306099/article/details/143776844

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！