(247) Segment Tree Query II

(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

https://segmentfault.com/a/1190000004674871

与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);
    }

http://www.cnblogs.com/EdwardLiu/p/5174965.html

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);

    }

Read full article from (247) Segment Tree Query II