树状数组简要总结

1.问题描述

单点修改，区间查询
多了树状数组也干不了，接下来全文描述的是单点加，区间和查询

2.算法原理

树状数组维护的是[1,n]的区间和，也就是前缀和，实际使用的时候（求[l,r]的区间和）还需要差分一下
也就是：sum(l,r) = sum(1,r) - sum(1,l-1)

现在来看一个家喻户晓的结论：任何一个数都可以化作2的幂的和
用这个思想，比如一个区间长度是7，那么可以分成区间长度4，2，1的三个区间，如果区间的起始位置不确定，那么这样没法给出一个方便的数据结构，但是我们可以利用差分计算区间和，所以可以所以区间的起点都从编号1开始
以7为例：[1,7] = [1,4] + [5,6] + [7,7]
区间长度分别是4，2，1
假如我们换一种区间的分配方式可以吗？ [1,7] = [1,1] + [2,3] + [4,7]
区间长度分别是1，2，4

乍一看很合理，但是这样仅对于7合理，如果你想算[1,6]了，会发现没维护[1,2]这个区间的值，所以区间长度2的整数次幂从大到小的顺序进行维护，每个区间如果还可再分，就同样的思想递归（此时你就会发现你递归着建树了），也就是上图中的树状数组，并且这个树的节点个数就是数组的长度，非常地节省空间，时空均比线段树占优势（时间上常数小）

从左往右区间长度是递减的，那么对于给定区间，查询区间和，区间长度每次减小的幅度就是2的幂的和中最小的那一项，称之为“lowbit”，可以巧妙利用计算机二进制的补码表示轻易获得

并且有：对于每个节点x，它的父节点是x+lowbit(x) 因为这样加完之后，恰好x进位

也就是说：无论是单点修改还是区间查询，每次变动幅度都是lowbit(x)

3.代码实现

#include<iostream>
using namespace std;
int sum[500001],n,m;

//求二进制下最末一个1
int lowbit(int x)
{
	return x&(-x);
}

//单点加
void add(int idx,int x)
{
	for(int i=idx;i<=n;i+=lowbit(i))
	sum[i]+=x;
}

//[1,x]和查询
int query_sum(int x)
{
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i))
	ans+=sum[i];
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		add(i,x);
	}
	for(int i=1;i<=m;i++)
	{
		int order;
		cin>>order;
		if(order==1)
		{
			int x,k;
			cin>>x>>k;
			add(x,k);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<(query_sum(y)-query_sum(x-1))<<endl;
		}
	}
	return 0;
}