lowbit:

lowbit(x)=x&(-x)

樹狀數(shù)組：

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

數(shù)組

在O(1)的時間復雜度實現(xiàn)單點加：

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

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

查詢前x項的和操作：

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

單點加操作：

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

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

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

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