【算法】树状数组
2021-01-20 05:13
标签：模板 位置 data owb amp lan res line math \(C[i]\)表示数组\(A\)中的一段连续和，具体是哪一段，由下式确定： \(C[i]=A[i-2^k+1]+A[i-2^k+2]+...+A[i]\) 其中\(k\)为\(i\)的二进制数中从最低位到最高位连续零的长度，如对于\(8(1000)\)，\(k=3\) \(SUM[i]\)表示数组\(A\)的前\(i\)项和，计算式：\(SUM[i]=C[i]+C[i-2^{k}]+C[i-2^{k}-2^{k}]+...\) 其中\(2^{k}=i\&(-i)\) ，记作lowbit. 当\(A[i]\)更新时，受影响的有\(C[i+2^k]、C[i+2^k+2^k].....\) 【算法】树状数组 标签：模板 位置 data owb amp lan res line math 原文地址：https://www.cnblogs.com/streamazure/p/12903092.html树状数组
求和
更新
模板
int n;
int a[1005],c[1005]; //原数组和树状数组
int lowbit(int x) return x&(-x);
void updata(int i,int p){ //在i位置加上p
while(i 0){
res += c[i];
i -= lowbit(i);
}
return res;
}