Fenwick Tree 主要用于求各种维度的区间 sum,主要缺点在于建树时间长于 segment tree ,需要 O(n log n) 时间,还有和面试官解释的时候比较麻烦。。主要优点是好写,而且非常容易扩展到多维情况。
The two's complement of an N-bit number is defined as the complement with respect to 2^N; in other words, it is the result of subtracting the number from 2^N
在图上的树状结构中,任意一个点的 parent 等于其 binary representation 的最右一个 1 的 bit 上再 +1; 比如 3 = 0011 ,parent = 8 = 0100.
从 child 到 parent 这条线,代表着更新。上图的结构,也是相对于更新操作的 tree structure.
而 query 是另一种结构和搜索过程,是一步一步把 index 的 binary representation 拆出来,变成 13 = 001011 ,对应 BIT[001000] + BIT[000010] + BIT[000001] 的过程
Copy public class NumArray {
int [] fenwickTree;
int length;
int [] arr;
public NumArray ( int [] nums) {
length = nums . length ;
arr = new int [length];
fenwickTree = new int [length + 1 ];
for ( int i = 0 ; i < length; i ++ ){
update(i , nums[i]) ;
}
}
void update ( int i , int val) {
int diff = val - arr[i];
arr[i] = val;
for ( int index = i + 1 ; index <= length; index += (index & - index)){
fenwickTree[index] += diff;
}
}
private int getSum ( int i){
int sum = 0 ;
while (i > 0 ){
sum += fenwickTree[i];
i -= (i & - i);
}
return sum;
}
public int sumRange ( int i , int j) {
return getSum(j + 1 ) - getSum(i) ;
}
}
这题如果 int[][] nums 直接指向 matrix 会在 update 操作之后得到错误结果,目前我还没仔细想为什么。。。稳妥起见还是老老实实新建一个吧。
增加维度的逻辑非常简单,只需要把对应的 tree array 增加维度就可以了,这时候新的getSum(i,j)所代表的是,从 (0,0) 开始到 (i,j) 的矩形范围内的 sum,相对于一维 fenwick tree 中的 (0, index) 的和。
Copy public class NumMatrix {
int [][] fenwickTree;
int [][] nums;
int rows;
int cols;
public NumMatrix ( int [][] matrix) {
if (matrix == null || matrix . length == 0 ) return ;
rows = matrix . length ;
cols = matrix[ 0 ] . length ;
fenwickTree = new int [rows + 1 ][cols + 1 ];
nums = new int [rows][cols];
for ( int i = 0 ; i < rows; i ++ ){
for ( int j = 0 ; j < cols; j ++ ){
update(i , j , matrix[i][j]) ;
}
}
}
public void update ( int row , int col , int val) {
int diff = val - nums[row][col];
nums[row][col] = val;
for ( int i = row + 1 ; i <= rows; i += (i & - i)){
for ( int j = col + 1 ; j <= cols; j += (j & - j)){
fenwickTree[i][j] += diff;
}
}
}
private int getSum ( int row , int col){
int sum = 0 ;
for ( int i = row; i > 0 ; i -= (i & - i)){
for ( int j = col; j > 0 ; j -= (j & - j)){
sum += fenwickTree[i][j];
}
}
return sum;
}
public int sumRegion ( int row1 , int col1 , int row2 , int col2) {
return getSum(row2 + 1 , col2 + 1 ) + getSum(row1 , col1) -
getSum(row1 , col2 + 1 ) - getSum(row2 + 1 , col1) ;
}
}