繁忙的公路

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int N;
int d[1000005];//树状数组
int LowBit(int x)//返回参数转为二进制后，最后一个1位置代表的
{
    return x&(-x);
}
void update(int x,int num)//表示在x点增加了num辆，修改树状数组
{
    while(x<=N)
    {
        d[x]+=num;
        x+=LowBit(x);
    }
}
long long sum(int x)//使用树状数组对原数组求和
{
    long long s=0;
    while(x>0)
    {
        s+=d[x];
        x-=LowBit(x);
    }
    return s;
}
int main()
{
    int tmp1,i,tmp2,m;
    char command;
    cin>>N;//标记点的数量
    for(i=0; i<=N; i++)d[i]=0;
    cin>>m;//命令的数量
    for(i=1; i<=m; i++)
    {
        cin>>command>>tmp1>>tmp2;
        if(command=='H')
        {
            update(tmp1,tmp2);
        }
        else if(command=='Q')
        {
            cout<<sum(tmp2)-sum(tmp1-1)<<endl;
        }
    }
    return 0;
}

这段代码也就包括了树状数组的基本操作集，树状数组可以高效的计算动态数列的前缀和。