树状数组

树状数组

树状数组 前缀和、修改一个元素的时间复杂度均为O(logn), 适合需要频繁进行区间和查询的情况

---

C++实现

int a[500001];
 
inline int lowbit(int x)
{
    return x&(-x);
}
 
void up(int x,int val)
{
    for(; x<=maxn; x+=lowbit(x)) a[x]+=val;
}
 
 
int _sum(int x)
{
    int sum=0;
    for(; x>0; x-=lowbit(x)) sum+=a[x];
    return  sum;
}