Segment Tree 线段树
Efficient and easy segment trees
线段树是一种平衡二叉树，对于每一个非叶子节点[a, b]，左子树表示区间[a, (a+b)/2], 右子树表示区间[(a+b)/2 + 1, b]。叶节点树木为N，即线段区间的长度。
基本操作：
建立O(n), 单点修改O(lgn), 单点查询O(lgn)*, 区间修改O(lgn)·
int[] tree;
int n;
public NumArray(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 2];
buildTree(nums);
}
}
private void buildTree(int[] nums) {
for (int i = n, j = 0; i < 2 * n; i++, j++)
tree[i] = nums[j];
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
void update(int pos, int val) {
pos += n;
tree[pos] = val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
// parent is updated after child is updated
tree[pos / 2] = tree[left] + tree[right];
pos /= 2;
}
}
public int sumRange(int l, int r) {
// get leaf with value 'l'
l += n;
// get leaf with value 'r'
r += n;
int sum = 0;
while (l <= r) {
if ((l % 2) == 1) {
sum += tree[l];
l++;
}
if ((r % 2) == 0) {
sum += tree[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
Binary Index Tree 树状数组
推荐 ✨BIT
设B[ ]表示数组A[ ]的树状数组，B[i]表示A[i - 2^k]到A[i]的和。 k 表示i二进制表示法末尾0的个数。 👆图。-> B[i]存有i最后一位1所在的位置对应数量的A内元素的和。比如 8(2) = 1000, B[8] = A[1] + A[2] +…+ A[8].
基本操作：
Sum & Update O(lgn)
lowBit(find the 0s in tail of index):
index & (-index);
// OR
index & (index ^ (index - 1));
Update(update A[idx]):
void update(int idx, int val){
while(idx <= N) {
tree[idx] += val;
idx += (idx & -idx);
}
}
Sum(sum to A[idx]):
int sum(int idx){
int sum = 0;
while(idx > 0){
sum += tree[idx];
idx -= idx & (-idx);
}
return sum;
}
对比？
简而言之，BIT更加灵活，需要的空间较少，适合单个元素或者连需求和情况。修改区间则效率较低。
负数的二进制表示：wiki
2‘ complement: 1’s complement + 1 补码
1’s complement: 反码
PS. LC segment tree 和 BIT 分类，题目是一样的 :)