前缀和与树状数组
首先让我们从一道题目入手
对于一个算法新手来说，可能只会想到暴力做法
每次求范围都进行一次for循环
whilie(m--)
{
cin>>l>>r;
int sum=0;
for(int i=;i<=r;i++) sum+=a[i];
cout<思考一下暴力做法的时间复杂度，会发现是O(mn)，在极端的情况下是10的12次方，会超时
这时候就是需要算法优化——前缀和算法
我们可以把把a[N]看成是一个数列，求出每一位的前n项和s[N]。
之后当我们再求某个区间内的和时，就不需要再进行一次for循环。
直接用前r个数的和，减去前l个数的和，
得到的就是l与r之间数的和。
S[i] = a[1] + a[2] + ... a[i]；
a[l] + ... + a[r] = S[r] - S[l - 1]；
//最最重要的是思想
for(int i=1;i<=n;i++)
S[i] = S[i-1]+a[i];
//每个i都有其对应的前缀和什么是前缀和
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 S[i]为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换
s[0] = 0
s[1] = s[0]+a[1]
前缀和的作用
快速求出元素组中某段区间的和
这时候我们要思考一个问题，在这个题目中，是根据原始的a[N]数组算出的前缀和，在之后的每次查询中，原数组a[N]和前缀和s[N]都没有发生变化。倘若我们改变原数组a[N]中某位数的值,我们又该如何求某段区间的和哪
动态求连续区间和
我们可以用刚刚学的知识——前缀和
题目中a[N]每改变一次，我们就更新她的前缀和
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--)
{
int k,a,b;
cin>>k>>a>>b;
if(k==0)
{
cout<再思考一下时间复杂度，和上一题的暴力枚举做法一样，O(mn),显然超时
那么，该怎么进行优化哪
根据经验，至少要把时间复杂度优化到nlogn；
在上面这段代码中，循环m次是不可能改变的，因为就是要进行m次询问嘛
要想下如何优化这部分代码，
for(int i=a;i<=n;i++) s[i]+=b;也就是优化前缀和
因此
伟大的Peter M. Fenwick想出了树状数组，用于高效计算数列的前缀和， 区间和。
树状数组可以解决的问题
可以解决大部分基于区间上的更新(单点修改）以及求和问题（区间查询)。
如果非要一句话说明树状数组 ：将一个前缀和划分成多个子序列的和
按照Peter M. Fenwick的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。
采用这个想法，我们可将一个前缀和划分成多个子序列的和，而划分的方法与数的2的幂和具有极其相似的方式。
C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i];
//k为i的二进制中从最低位到高位连续零的长度
//返回x的最后一位1
int lowbit(int)
{
return x & -x;
}
//add(x,y):在x位置加上y，并将后面相关联的位置也加上y
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=y;
}
//query(x):询问x的前缀和
int query(int x)
{
int 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]);
while(m--)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==0)
{
int ans=query(y)-query(x-1);
printf("%d\n",ans);
}
else add(x,y);
}
return 0;
}这时的时间复杂度为O(mn)
结束~~~
若有收获，就点个赞吧~~~