lowbit:

lowbit(x)=x&(-x)

樹狀數(shù)組：

樹狀數(shù)組的功能：

數(shù)組

在O(1)的時(shí)間復(fù)雜度實(shí)現(xiàn)單點(diǎn)加：

在O(lng n)的時(shí)間復(fù)雜度實(shí)現(xiàn)查詢前綴和：

樹狀數(shù)組的定義：

查詢前x項(xiàng)的和操作：

ll query(int x){ll s=0;for( ; x; x-=x&(-x)){s+=c[x];}return s;
}

單點(diǎn)加操作：

//原數(shù)組長度為n
void modify(int x,ll s){for(;x<=n;x+=x&(-x)){c[x]+=s;}//如果需要別忘了把元素組對應(yīng)的一位也進(jìn)行變換
}

構(gòu)造一個樹狀數(shù)組：

//原數(shù)組長度為n
scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);modify(i,a[i]);}

在輸入元素的每一位時(shí)對應(yīng)的在樹狀數(shù)組的位置加上該值。