前缀查询

一句话理解

前缀查询：沿 i-=lowbit(i) 向下累加。

为什么要学

sum(1..i)。

讲解

while(i) s+=c[i], i-=lowbit(i)。

例子

int sum(int i) {
    int s = 0;
    for (; i; i -= i & -i) s += c[i];
    return s;
}

把前缀拆成几段树状区间。

常见错误

• i 减成负数。
• 查询 0。