树状数组

第一个函数；

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<         }
    }
}