树状数组原理
功能:
①快速求前缀和 O ( l o g n ) O(logn) O(logn)
②修改某一个数 O ( l o g n ) O(logn) O(logn)
操作：
①：建树
void add(int x, int c) {
//树状数组的插入操作
for (int i = x;i <= n;i += lowbit(i))tr[i] += c;
}
②：区间查询：1 ~ x 前缀和
for(int i = x;i <= n;i += lowbit(i))res += c;
③：单点修改：
for(int i = x;i;i -= lowbit(i))tr[i] += c;
字节跳动成长空间 617人发布
投递字节跳动等公司10个岗位 >
