树状数组

一、 树状数组介绍

• 黑色数组代表原来的数组（下面用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];

C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i];   //k为i的二进制中从最低位到高位连续零的长度

SUMi = C[i] + C[i-2k1] + C[(i - 2k1) - 2k2] + .....；//求和

 

二、建立树状数组

 

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>

using namespace std;
#define ll long long
#define il inline
#define lowbit(x) x&-x

int a[1005], tree[1005], n; //对应原数组和树状数组

void add(int i, int k) {    //在i位置加上k
    while (i <= n) {
        tree[i] += k;
        i += lowbit(i);
    }
}

int getSum(int i) {        //求A[1 - i]的和
    int res = 0;
    while (i > 0) {
        res += tree[i];
        i -= lowbit(i);
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        add(i, a[i]);
    }
    printf("%d ", getSum(3));
}