概念

树状数组(Binary Indexed Tree || Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和。

在本文中，如果C[i + j] 可以表示成 C[i] 与其他C[]的和，则称C[i+j]为C[i]的父节点。如果C[i] 与 C[j] 没有重叠的A[k]，则称C[j]为C[i]的子节点(j<i)。

原理

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

C9 = A9

首先介绍一个函数 int lowbit(int x);

这个函数的作用是返回2^{x的二进制形式下末尾零的个数}。

比如 (5)₁₀=(101)_2，是末尾有0个2，因此返回1。

比如 (8)₁₀=(1000)_2，是末尾有3个2，因此返回8。

再介绍lowbit()函数的用途。

x + lowbit(x) 是此节点的最近父节点，比如6的最近父节点是8，7的最近子节点也是8。

x – lowbit(x) 是此节点的最近子节点，比如8的最近子节点是0，6的最近子节点4。

构造数组C(修改数组C)

假设一开始A[3] = 1，现在我们要把A[3]修改为2，因此要把所有包含A[1]的C[i]加一。

那么，哪一些C[i]是包含A[3]的呢。我们可以观察到，A[i]第一次出现是出现在C[i]。

比如A[1]第一次出现在C[1]中，A[2]第一次出现在C[2]中。

因此，我们只要从C[3]开始加一即可，而下一个加一的节点是谁哪一个？是C[3]的最近父节点。

void change(int i, int x) {
	//i为第几个要修改的元素
	//x为修改后与修改前的差值
	while (i <= n) {
		c[i] += x;
		i = i + lowbit(i);//最近父节点
	}
}

求数组A[i]的和

假设求前i个A[i]的和，那么我们只需要从C[i]开始累加，每次加此节点的最近子节点即可。

注意！

终止条件不能写为 i >= 0，因为lowbit(0) = 0，会陷入死循环

int getsum(int i) {
	int sum = 0;
	while (i > 0) {
		sum += c[i];
		i = i - lowbit(i);//最近子节点
	}
}

lowbit函数

lowbit函数的具体原理，如果了解二进制数值的有关知识，就很容易理解了，在这就不过多赘述了，只把源代码贴上来。

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

完整代码

#include <cstdio>
#include <iostream>
#include <stack>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int n;
int a[100];
int c[100];
int lowbit(int x) {
	return x & (-x);
}
void change(int i, int x) {
	//i为第几个要修改的元素
	//x为修改后与修改前的差值
	while (i <= n) {
		c[i] += x;
		i = i + lowbit(i);//最近父节点
	}
}
int getsum(int i) {
	int sum = 0;
	while (i > 0) {
		sum += c[i];
		i = i - lowbit(i);//最近子节点
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int t;
		cin >> t;
		change(i, t);
	}
	return 0;
}

View Code

树状数组

原文：https://www.cnblogs.com/woxiaosade/p/10500585.html