树状数组模板

//树状数组

#include<iostream>
using namespace std;
const int N=1e5+10;

int a[N],c[N];
int lowbit(int x) //lowbit()表示 x 的二进制数的最后一位为1以及后面的0所表示的整数
{                 //例：12 二进制表示为 1100 ,lowbit(12)表示二进制数100表示的整数，所以为4
    return x&-x;
}

/*
**update函数含义
**原始数组x位置增加v后，更新c数组
**n为数组边界
*/
void update(int n,int x,int v,int c[])
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        c[i]+=v;
    }
}

int getsum(int c[],int x)
{
    int sum=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        sum+=c[i];
    }
    return sum;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        update(9,i,a[i],c);
    }
    cout<<getsum(c,5)<<'\n';
    cout<<getsum(c,8)-getsum(c,5);
    return 0;
}