朴素树状数组（单点修改，区间查询（前缀和））

const int N = 5e5+10;
int a[N],tr[N];

int lowbit(int x)
{
    return x & -x;
}

int sum(int x)//求1~x的所有和
{
    int res = 0;
    for (int i = x ; i ; i -= lowbit(i))
        res += tr[i];
    return res;
}

void add(int x,int c)//在x位置加上c
{
    for(int i = x ; i <= N ; i += lowbit(i))
        tr[i] += c;
}

树状数组还可以通过变成差分数组来实现区间修改、单点查询

//O(N)建立树状数组方式，a为前缀和数组
void build()
{
    for (int i = 1 ; i < N ;i++)
    tr[i] = a[i] - a[i - lowbit(i)];
}