第一个函数；
int lowbit(int x)
{
return x&(-x);
}
这个函数主要是用来求的是某个点管辖范围；
x&(-x);这个东西的由来就不说了。。。灰常奇妙啊。。
如果是x+=x&(-x);就是得到的改点的父节点的值；比如x=4时；就能得到8；
而x-=x&(-x)的话，就是得到x这个点的管辖区间的下个区间的管辖点；
比如说，x=7,代入后6；不断循环到0能依次得到 6.。。4.；
把他们所有的管辖区间正好是1....7；
第二个函数
void update(int x,int num)
{
while(x<=N)
{
d[x]+=num;
x+=lowbit(x);
}
}
这个函数，是用来修改树状数组的；
如果是一般的算法只用修改改点就可；但是树状数组必须修改所有改点被管辖的区间；
比如把a数组的 a[2]减去1，（令N=16）；则所有2被管辖的点有4，8，16都应该减去1；
就是调用函数 update（2，-1）；
第三个函数
int getSum(int x)
{
int s=0;
while(x>0)
{
s+=d[x];
x-=lowbit(x);
}
return s;
}
这个函数就是求区间和了。。比如getSum（7）的话，就是求a[1]+a[2]+...a[7];
上面是最基本的用法；要学习树状数组必须把上面的过程原理搞明白；
树状数组在区间求和问题上有大用，其三种复杂度都比线段树要低很多……
树状数组主要的功能是降低算法的时间复杂度。
#include
//#include
#include
//#include
using namespace std;
//long long ans[100100]= {}; //这个题其实用的是树状数组的概念
int d[100102]={};
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int num,int N)
{
while(x<=N)
{
d[x]+=num;
x+=lowbit(x);
}
}
int getSum(int x)
{
int s=0;
while(x>0)
{
s+=d[x];
x-=lowbit(x);
}
return s;
}
int main()
{
int n;
while(cin>>n)
{
int p,q;
cin>>p;
while(p--)
{
int L,R,X;
cin>>L>>R>>X;
for(long i=L;i<=R;i++)
update(i,X,n);
}
cin>>q;
while(q--)
{
int L,R;
cin>>L>>R;
int sum=getSum(R)-getSum(L-1);
cout<
}
}