不建tree直接用int[] 表示tree
parent -> (n - 1) / 2
leftChild -> 2 * n + 1
rightChild -> 2 * n + 2
有空开心的时候写一下
三刷 07/2022
Version #2 Segment Tree
Time - constructor O(N), update O(logN), query O(logN)
Space O(N)
Runtime: 138 ms, faster than 61.04% of Java online submissions for Range Sum Query - Mutable.
Memory Usage: 133.4 MB, less than 34.89% of Java online submissions for Range Sum Query - Mutable.
class NumArray {
private Node root;
class Node {
int start, end;
int sum;
Node left, right;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
}
private Node buildTree(int[] nums, int start, int end) {
Node curr = new Node(start, end);
if (start == end) {
curr.sum = nums[start];
return curr;
}
int mid = start + (end - start) / 2;
curr.left = buildTree(nums, start, mid);
curr.right = buildTree(nums, mid + 1, end);
curr.sum = curr.left.sum + curr.right.sum;
return curr;
}
private void updateNum(Node node, int index, int val) {
if (node.start == node.end && node.start == index) {
node.sum = val;
return;
}
int mid = node.start + (node.end - node.start) / 2;
if (index <= mid) {
updateNum(node.left, index, val);
} else {
updateNum(node.right, index, val);
}
node.sum = node.left.sum + node.right.sum;
}
private int query(Node node, int start, int end) {
if (node.start == start && node.end == end) {
return node.sum;
}
int mid = node.start + (node.end - node.start) / 2;
if (start > mid) {
return query(node.right, start, end);
} else if (end <= mid) {
return query(node.left, start, end);
}
return query(node.left, start, mid) + query(node.right, mid + 1, end);
}
public NumArray(int[] nums) {
this.root = buildTree(nums, 0, nums.length - 1);
}
public void update(int index, int val) {
updateNum(root, index, val);
}
public int sumRange(int left, int right) {
return query(root, left, right);
}
}
Version #2 Segment Tree
20.15 %
这个写法是对的！
每次在query的时候都要缩小query的范围，当query和tree的start end正好重合时候就直接返回
以前写的一个是query范围不变，那base case就变成了start == end, 这样每次都必须找到Leaf才能停止，时间复杂度就变成了O(n) 而不是logn
public class NumArray {
class SegmentTree {
int start, end;
SegmentTree left, right;
int sum;
public SegmentTree(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
}
}
private SegmentTree root;
public NumArray(int[] nums) {
this.root = init(nums, 0, nums.length - 1);
}
public SegmentTree init(int[] nums, int start, int end) {
if (start > end) return null;
if (start == end) return new SegmentTree(start, end, nums[start]);
int mid = start + (end - start) / 2;
SegmentTree left = init(nums, start, mid);
SegmentTree right = init(nums, mid + 1, end);
SegmentTree root = new SegmentTree(start, end, left.sum + right.sum);
root.left = left;
root.right = right;
return root;
}
public void update(int i, int val) {
updateTree(i, root, val);
}
private void updateTree(int i, SegmentTree root, int val) {
// out of range
if (i < root.start || i > root.end) return;
if (root.start == root.end) {
root.sum = val;
return;
}
//i <= mid
if (i <= root.left.end) {
updateTree(i, root.left, val);
} else {
updateTree(i, root.right, val);
}
root.sum = root.left.sum + root.right.sum;
}
public int sumRange(int i, int j) {
return sumRangeTree(i, j, root);
}
private int sumRangeTree(int left, int right, SegmentTree root) {
if (right < root.start || left > root.end) return 0;
//in Range -> start, left, right, end
if (root.start == left && root.end == right) return root.sum;
int mid = root.start + (root.end - root.start) / 2;
if (right <= mid) {
return sumRangeTree(left, right, root.left);
} else if (left >= mid + 1) {
return sumRangeTree(left, right, root.right);
} else {
return sumRangeTree(left, mid, root.left) + sumRangeTree(mid + 1, right, root.right);
}
}
}
Version #1 Binary Indexed Tree
二刷
每次的update事实上分两步
第一步是update tree with diff
这里的treeIndex = i+1
第二步是update nums array
62.91 %
class NumArray {
int[] sums;
int[] nums;
int n;
public NumArray(int[] nums) {
n = nums.length;
sums = new int[n + 1]; // 1 indexed
this.nums = nums;
for (int i = 0; i < n; i++) {
updateTree(i, nums[i]);
}
}
public void update(int i, int val) {
int diff = val - nums[i];
updateTree(i, diff);
nums[i] = val;
}
private void updateTree(int i, int val) {
i++;
while (i <= n) {
sums[i] += val;
i += (i & (-i));
}
}
public int sumRange(int i, int j) {
return prefix(j) - prefix(i - 1);
}
private int prefix(int i) {
int sum = 0;
i++;
while (i > 0) {
sum += sums[i];
i -= (i & (-i));
}
return sum;
}
}
一刷
这个tree有一个神奇的性质
i = i + (i & (-i)); 找到的是它右上最近parent的index
i = i - (i & (-i)); 找到的是它左上最近parent的index
注意number array的index是0 -> length - 1
而Binary Indexed Tree 的index 是 1 -> length
所以每次操作 ti = ni + 1
写了一个晕了的bug
传进来的nums array是initialize 用的array
而数据结构本身同样需要一个nums array来记录每一个点的值
因为BIT记录的是leftSum(the value of the node itself is included)，所以需要一个nums array来记录node本身的value
在update的时候的diff也是value 和nums[ni] 之间的差
Space O(n)
Time construction O(nlogn)
query O(logn)
update O(logn)
50.87 %
public class NumArray {
int[] nums;
int[] leftSum;
public NumArray(int[] nums) {
if (nums == null) return;
this.nums = new int[nums.length];
this.leftSum = new int[nums.length + 1];
//ni -> index of nums array
//ti -> index of tree
for (int ni = 0; ni < nums.length; ni++) {
update(ni, nums[ni]);
this.nums[ni] = nums[ni];
}
}
public void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
// ni -> ti
i += 1;
while (0 < i && i < leftSum.length) {
leftSum[i] += diff;
i = i + (i & (-i));
}
}
private int prefixSum(int i) {
i += 1;
int sum = 0;
while (0 < i && i < leftSum.length) {
sum += leftSum[i];
i = i - (i & (-i));
}
return sum;
}
public int sumRange(int i, int j) {
return prefixSum(j) - prefixSum(i - 1);
}
}
No comments:
Post a Comment