前言
众所周知，通过前缀和，我们可以很快的在一个很大的数组中求出区间和，但是如果想要去修改数组中的一个数的值，前缀和就无法实现。所以来学习一个新的数据结构：树状数组
（文章中关于树状数组的截图来自于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;
}
}
