树状数组基础

基础概念

树状数组是用数组来模拟树形结构，可以解决大部分基于区间上的更新以及求和问题。树状数组中修改和查询的复杂度都是O(logN)，树状数组一般用于「单点更新」和「前缀和查询」
黑色数组代表原来的数组（下面用A[i]代替），红色树代表我们的树状数组(下面用C[i]代替)。树状数组每个位置只有一个方框，每个位置存的就是子节点的值的和：

• C[1] = A[1];
• C[2] = A[1] + A[2];
• C[3] = A[3];
• C[4] = A[1] + A[2] + A[3] + A[4];
• C[5] = A[5];
• C[6] = A[5] + A[6];
• C[7] = A[7];
• C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

「 这棵树的节点值是有规律的 」

其中，k 为 i 的二进制数中从最低位到高位的连续零的长度，举个例子

• 
  • 
• 
  • 

• 

  • 

    SUM

    「 前 i 项的和也是有规律的 」
    
    其中，k1 是 i 的二进制数中从最低位到高位的连续零的长度，而 k2 是 i - 2^k1 的二进制数中从最低位到高位的连续零的长度，以此类推，同样举个例子

• 

lowBit

「 i 的二进制数中从最低位到高位的连续零的长度应该如何求取」

还有一种更简单的公式

• 当 i 为 0 时，结果为 0
• 当 i 为奇数时，结果为 1

• 当 i 为偶数时，结果为 2^k

  update

  「如何更新某个点的值」
  如果我们更新了某个A[i]的值，则会影响所有包含A[i]的树状数组的位置，A[i]包含于
  
  其中，k1 是 i 的lowbit， k2 是 i + 2^k1 的lowbit，以此类推，同样举个例子

• 例如A[1]包含于

建立一个树状数组

int n;
int[] c = new int[n + 5];
public int lowbit(int i){
    return i & (-i);
}
public void update(int i, int k){ 
    //在i的位置加上k
    //即a[i]的值修改，会影响若干个c的值
    while(i <= n){
        c[i] += k;
        i += lowbit(i);
    }
}
public int query(int i){
    //求sum_i，即a[1]到a[i]的和
    int sum = 0;
    while(i > 0){
        sum += c[i];
        i -= lowbit[i];
    }
    return sum;
}

树状数组详解