(247) Segment Tree Query II
https://segmentfault.com/a/1190000004674871
http://www.cnblogs.com/EdwardLiu/p/5174965.html
Read full article from (247) Segment Tree Query II
For an array, we can build a
SegmentTree
for it, each node stores an extra attribute count
to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)
Design a
query
method with three parameters root
, start
and end
, find the number of elements in the in array's interval [start, end] by the given root of value SegmentTree.
For array
[0, 2, 3]
, the corresponding value Segment Tree is: [0, 3, count=3]
/ \
[0,1,count=1] [2,3,count=2]
/ \ / \
[0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
query(1, 1)
, return 0
query(1, 2)
, return 1
query(2, 3)
, return 2
query(0, 2)
, return 2
与Query I所不同的是,Query II对所给区间内的元素个数求和,而非筛选。这样就会出现
start <= root.start && end >= root.end
的情况,视作root本身处理。 public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) return 0;
if (root.start == root.end || (start <= root.start && end >= root.end)) return root.count;
return query(root.left, start, end) + query(root.right, start, end);
}
20 public int query(SegmentTreeNode root, int start, int end) { 21 // write your code here 22 if (root == null || root.end < start || root.start > end) return 0; 23 if (root.start>=start && root.end<=end) return root.count; 24 int mid = (root.start + root.end)/2; 25 if (end <= mid) return query(root.left, start, end); // no need 26 else if (start > mid) return query(root.right, start, end); // no need 27 else return query(root.left, start, mid) + query(root.right, mid+1, end); 28 }https://codesolutiony.wordpress.com/2015/05/12/lintcode-segment-tree-query-ii/
public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) {
return 0;
}
if (root.start == root.end || (start <= root.start && end >= root.end)) {
return root.count;
}
return query(root.left, start, end) + query(root.right, start, end);
}