Binary Indexed Tree 主要是为了存储数组前缀或或后缀和，以便计算任意一段的和。其优势在于可以常数时间处理更新（如果不需要更新直接用一个数组存储所有前缀/后缀和即可）。
空间复杂度O(n). 其中每个元素，存储的是数组中一段（起始元素看作为1而非0）的和:
假设这个元素下标为i，找到i的最低位1，从最低位1开始的低部表示的是长度，去除最低位1剩下的部分加上1表示的是起始位置，例如:
8二进制表示为100
最低位1也是最高位，从1开始的低部也即100本身，因此长度为8.
去除1以后，剩下为0，加上1以后为1。所以sum[8]表示的是从第1个元素开始的8个元素的和.
又比如11的二进制表示为1011
最低位1，因此表示的段长度为1。
去掉1以后剩下部分为1010，因此起始元素为第11个元素。所以sum[11]表示的就是原数组的第11个元素。
求i的最低位1(LSB)可以使用如下位运算：
i & (-i)
求1..i之和，以11为例
sum[11] = sum[8] + sum[10] + sum[11] 也即 0..8之和 + 9, 10之和 + 11。我们可以从最低位开始相加：
int sum = 0; while (i > 0) sum += A[i], i -= LSB(i); return sum;
更新i的值，需要更新所有受影响的和,从sum[i]开始，逐渐扩大i的范围
while (i < SIZE) A[i] += k, i += LSB(i);
比如元素5被更新了，5表示为2进制是101,
那么我们首先更新元素5本身，
然后，5所在的2个元素的小区间:5,6也需要被更新也即 5 + LSB(5) = 6 被更新。
然后，更新5所在的更大的区间，1..8，也即: 6 + LSB(6) = 8。注意，并不存在5..8这样一个单独的4元素区间。每个区间的后半部分可以用这个区间减去前半部分得到：sum 5..8 = sum[8] – sum[4]。
上述代码来自Wiki
最后，求任意区间i..j的值可以由sum[j] – sum[i]得到。
以LeetCode 307. Range Sum Query – Mutable为例，以下为源码：
class NumArray{ public: // Binary Index Tree (Fenwick Tree) NumArray(vector<int> nums) { _nums = vector<int>(nums.size(), 0); sums = vector<int>(nums.size() + 1, 0); len = sums.size(); for(int i = 0; i < len - 1; i++){ update(i, nums[i]); } } void update(int i, int val) { int d = val - _nums[i]; _nums[i++] = val; while(i < len){ sums[i] += d; i += LBS(i); } } // [i+1, j+1] inclusive, so it should be sum[j+1] - sum[i] int sumRange(int i, int j) { return sumRange(++j) - sumRange(i); } private: vector<int> sums; vector<int> _nums; int len; inline int LBS(int &i){ return i & (-i); } inline int sumRange(int i){ int sum = 0; while(i){ sum += sums[i]; i -= LBS(i); } return sum; } };
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。