Binary Indexed Trees--树状数组
1 x&(-x) gives the last set bit in a number x. How?
Let’s say x = a1b(in binary) is the number whose last set bit we want to isolate.
Here a is some binary sequence of any length of 1’s and 0’s and b is some sequence of any length but of 0’s only. Remember we said we want the LAST set bit, so for that tiny intermediate 1 bit sitting between a and b to be the last set bit, b should be a sequence of 0’s only of length zero or more.
-x = 2’s complement of x = (a1b)’ + 1 = a’0b’ + 1 = a’0(0….0)’ + 1 = a’0(1...1) + 1 = a’1(0…0) = a’1b
Java代码：
int[] bitTree;
int lowbit(int x) {
return x&(-x);
}
public void constructTree(int[] nums) {
bitTree= new int[nums.length+1];
// Store the actual values in BITree[] using update()
for (int i=0; i<nums.length; i++)
updateBIT(i, nums[i]);
}
//update operation takes at most O(log2(n)) time.
public void updateBIT(int index, int val) {
// index in bitTree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse all ancestors and add 'val'
while (index < bitTree.length) {
//Add 'val' to current node of BI Tree
bitTree[index] += val;
//Update index to that of parent in update View
index += lowbit(index);
}
}
/**
* Returns sum of arr[0..index]. This function assumes
* that the array is preprocessed and partial sums of
* array elements are stored
*/
int read(int index) {
int sum = 0; // Iniialize result
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BITree[index]
while (index>0) {
// Add current element of BITree to sum
sum += bitTree[index];
// Move index to parent node in getSum View
index -= lowbit(index);
}
return sum;
}
Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
使用上面树状数组的实现：
void update(int[] nums,int i, int val) {
int diff = val - nums[i];
nums[i] = val;
updateBIT(i,diff);
}
int sumRange(int i, int j) {
return read(j) - read(i-1);
}