树状数组

概念

设定

• $A[i]$表示数组元素

• $C[i]$表示对应树状数组, 值为它所有子结点值和 $A[i]$总和

• $C[i]$中一定包含$A[i]$值

• $i$ 为奇数时, 有 $C[i] = A[i]$

graph BT;
    subgraph 数组
        A1[A1]
        A2[A2]
        A3[A3]
        A4[A4]
        A5[A5]
        A6[A6]
        A7[A7]
        A8[A8]
    end

    subgraph 树状数组
        C1((C1))
        C2((C2))
        C3((C3))
        C4((C4))
        C5((C5))
        C6((C6))
        C7((C7))
        C8((C8))
    end

    A1-->C1-->C2
    A2-->C2-->C4
    A3-->C3-->C4
    A4-->C4-->C8
    A5-->C5-->C6
    A6-->C6-->C8
    A7-->C7-->C8
    A8-->C8

区间范围

$C[i]$管辖数组 $A$ 一段连续区间和, 区间末尾元素是 $A[i]$

$C[i]$所管辖元素个数为$2^{k}$个($k$ 为 $i$ 二进制中最低位到最高位连续0长度)

• $C[8]$

$(8){10}$ =$(1000){2}$, 最低位到最高位连续 $0$ 长度为 $3$, 故 $k=3$, 管辖数有$2^{3}$个

$C[8]$是$8$ 个数($A[1]-A[8]$)和

• $C[5]$

$(5){10}$ =$(0101){2}$, 最低位到最高位连续 $0$ 长度为 $0$, 故 $k=0$, 管辖数有$2^{0}$个

$C[5]$是 $1$ 个数($A[5]$)和

• $C[4]$

$(4){10}$ =$(0100){2}$, 最低位到最高位连续 $0$ 长度为 $2$, 故 $k=2$, 管辖数有$2^{2}$个

$C[4$]是 4 个数($A[1]-A[4]$)和

给定 $i$, $C[i]$管辖范围$2^{k}$, $2^{k}$ = $i$ & $(-i)$

// 根据C[i]下标i获取管辖范围
int lowbit(int i){
    return i & (-i);
}

操作

更新

若更新 $A[i]$值, 则需更新 $C[i]$与它祖先节点值

• 更新 $A[1]$

更新所有包含$A[1]$的 $C[i]$, 即 $C[1]$和其祖先节点$C[2], C[4], C[8]$

$i = 1$

$C[1] += A[1]$

$lowbit(1) = 1; 1+lowbit(1) = 2 ; C[2]+=A[1]$

$lowbit(2) = 2; 2+lowbit(2) = 4 ; C[4]+=A[1]$

$lowbit(4) = 4; 4+lowbit(4) = 8 ; C[8]+=A[1]$

graph BT;
    subgraph 数组
        A1[**A1**]
        A2[A2]
        A3[A3]
        A4[A4]
        A5[A5]
        A6[A6]
        A7[A7]
        A8[A8]
    end

    subgraph 树状数组
        C1((**C1**))
        C2((**C2**))
        C3((C3))
        C4((**C4**))
        C5((C5))
        C6((C6))
        C7((C7))
        C8((**C8**))
    end

    A1 --> C1 --> C2
    A2 --> C2 --> C4
    A3 --> C3 --> C4
    A4 --> C4 --> C8
    A5 --> C5 --> C6
    A6 --> C6 --> C8
    A7 --> C7 --> C8
    A8 --> C8

• 更新 $A[6]$

更新所有包含 $A[6]$的 $C[i]$, 即 $C[6]$和其祖先节点 $C[8]$

$i = 6$

$C[6]+=A[6]$

$lowbit(6) = 2; 6+lowbit(6) = 8 ; C[8]+=A[6]$

graph BT;
    subgraph 数组
        A1[A1]
        A2[A2]
        A3[A3]
        A4[A4]
        A5[A5]
        A6[**A6**]
        A7[A7]
        A8[A8]
    end

    subgraph 树状数组
        C1((C1))
        C2((C2))
        C3((C3))
        C4((C4))
        C5((C5))
        C6((**C6**))
        C7((C7))
        C8((**C8**))
    end

    A1 --> C1 --> C2
    A2 --> C2 --> C4
    A3 --> C3 --> C4
    A4 --> C4 --> C8
    A5 --> C5 --> C6
    A6 --> C6 --> C8
    A7 --> C7 --> C8
    A8 --> C8

// pos 更新位置
// value 增加或减少值
// len 数组长度
void UpdateValue(int pos, int value, int len){
    a[pos] += value;
    // i代表更新位置
    for(int i = pos; i <= len; i += lowbit(i)){
        c[i] += value;
    }
}

区间和

// 求A[1] ~ A[X]的和
int GetIntervalSum(int x){
    int sum = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        sum += c[i];
    }
    return sum;
}