GabWiki

Appearance

树状数组 ​

模板题：动态求连续区间和。

树状数组是一种可以以 O(log⁡n) 的时间复杂度完成 单点修改 和 区间查询 的，代码量小的数据结构。

Java
// 序列长度为n 序列输入至a[1...n]
int[] a, tr;

int lowbit(int x) {
    return x & -x;
}

// 把a[i]自增x
void add(int i, int x) {
    for (; i <= n; i += lowbit(i)) tr[i] += x;
}

// 求a[1...i]的累和
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tr[i];
    return sum;
}
// 序列长度为n 序列输入至a[1...n]
int[] a, tr;

int lowbit(int x) {
    return x & -x;
}

// 把a[i]自增x
void add(int i, int x) {
    for (; i <= n; i += lowbit(i)) tr[i] += x;
}

// 求a[1...i]的累和
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= lowbit(i)) sum += tr[i];
    return sum;
}