Summary of the Divide and Conquer based and Binary Indexed Tree based solutions


  • 111
    F

    Thanks for those contributing excellent ideas to this problem. Here is a quick summary of solutions based on either divide and conquer or binary indexed tree.

    To start, we already know there is a straightforward solution by computing each range sum and checking whether it lies in [lower, upper] or not. If the number of elements is n, we have n*(n+1)/2 such range sums so the naive solution will end up with O(n^2) time complexity. Now we are asked to do better than that. So what are the targeted time complexities in your mind? When I first looked at the problem, my instinct is that O(n) solution is too ambitious, so I will target at linearithmic-like (O(n*(logn)^b)) solutions. To get the logarithmic part, it's natural to think of breaking down the original array, and that's where the divide-and-conquer idea comes from.

    For this problem, we need some array to apply our divide and conquer algorithm. Without much thinking, we can do that directly with the input array (nums) itself. Since our problem also involves range sums and I believe you have the experience of computing range sums from prefix array of the input array, we might as well apply divide and conquer ideas on the prefix array. So I will give both the input-array based and prefix-array based divide&conquer solutions.

    Let's first look at input-array based divide&conquer solution. Our original problem is like this: given an input array nums with length n and a range [lower, upper], find the total number of range sums that lie in the given range. Note the range [lower, upper] and the input array are both fixed. Therefore each range sum can be characterized by two indices i1 and i2 (i1 <= i2), such that range sum S(i1, i2) is the summation of input elements with indices going from i1 up to i2 (both inclusive). Then our problem can be redefined in terms of the value ranges of i1 and i2. For example our original problem can be restated as finding the total number of range sums lying in the given range with 0 <= i1 <= i2 <= n - 1, or in a symbolic way T(0, n-1).

    Now if we break our original input array into two subarrays, [0, m] and [m+1, n-1] with m = (n-1)/2, our original problem can be divided into three parts, depending on the values of i1 and i2. If i1 and i2 are both from the first subarray [0, m], we have a subproblem T(0, m); if i1 and i2 are both from the second subarray, we have a subproblem T(m+1, n-1); if i1 is from the first subarray and i2 from the second (note we assume i1 <= i2, therefore we don't have the other case with i2 from first subarray and i1 from second), then we have a new problem which I define as C. In summary we should have:

    T(0, n-1) = T(0, m) + T(m+1, n-1) + C

    Now from the master theorem, the time complexity of the new problem C should be better than O(n^2), otherwise we make no improvement by applying this divide&conquer idea. So again, I will aim at linearithmic-like solutions for the new problem C: find the total number of range sums lying in the given range with each range sum starting from the first subarray and ending at the second subarray.

    First let's try to compute all such range sums. The way I did it was first computing the prefix array of the second subarray and the suffix array (or "backward" prefix array if you like) of the first subarray. Then I can naively add each element in the suffix array to all elements in the prefix array to obtain all the possible range sums. Of course you end up with O(n^2) solution, as expected. So how can we approach it with better time complexity?

    Here are the facts I observed: for each element e in the suffix array, we need to add it to all elements in the prefix array. But the order in which we add it doesn't matter. This implies that we can sort our prefix array. This can be done in O(nlogn) time. Now we have a sorted prefix array, do we still need to add the element e to all elements in the prefix array? The answer is no. Because our final goal is to compare the resulted range sums with the given range bounds lower and upper. It is equivalent to modifying the range bounds so we have new bounds (lower - e) and (upper - e) and leave the prefix array unchanged. Now we can compare these new bounds with the sorted prefix array, and I'm sure you can write your own binary search algorithm to do that. So for each element e in the suffix array, we can compute the modified range bounds and get the number of range sums in this new range in logn time. Therefore the total time will be O(nlogn). So in summary, our new problem C can be solved in O(nlogn) time and according to the master theorem, our original problem can be solved in O(n(logn)^2) time. The following is the complete java program:

    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0 || lower > upper) return 0;
        return countRangeSumSub(nums, 0, nums.length - 1, lower, upper);
    }
    
    private int countRangeSumSub(int[] nums, int l, int r, int lower, int upper) {
        if (l == r) return nums[l] >= lower && nums[r] <= upper ? 1 : 0;  // base case
    	
        int m = l + (r - l) / 2;
        long[] arr = new long[r - m];  // prefix array for the second subarray
        long sum = 0;
        int count = 0;
    	
        for (int i = m + 1; i <= r; i++) {
    	sum += nums[i];
    	arr[i - (m + 1)] = sum;	// compute the prefix array
        }
    	
        Arrays.sort(arr);  // sort the prefix array
    	
        // Here we can compute the suffix array element by element.
        // For each element in the suffix array, we compute the corresponding
        // "insertion" indices of the modified bounds in the sorted prefix array
        // then the number of valid ranges sums will be given by the indices difference.
        // I modified the bounds to be "double" to avoid duplicate elements.
        sum = 0;
        for (int i = m; i >= l; i--) {
    	sum += nums[i];  
    	count += findIndex(arr, upper - sum + 0.5) - findIndex(arr, lower - sum - 0.5);
         }
    	
        return countRangeSumSub(nums, l, m, lower, upper) + countRangeSumSub(nums, m + 1, r, lower, upper) + count;
    }
    
    // binary search function
    private int findIndex(long[] arr, double val) {
        int l = 0, r = arr.length - 1, m = 0;
    	
        while (l <= r) {
    	m = l + (r - l) / 2;
    		
    	if (arr[m] <= val) {
    	    l = m + 1;
    	} else {
    	    r = m - 1;
            }
        }
    	
        return l;
    }
    

    (Next two parts will come in answers due to the limitation of maximum length of characters )


  • 0
    F
    This post is deleted!

  • 23
    F

    Now let's turn to prefix-array based divide&conquer solution. You can find more info in posts given by @dietpepsi. Here is the gist of the algorithm.

    We have the prefix array(which I will call prefix) of the input array (nums). The prefix array will have n + 1 elements if nums has n elements. Likewise each range sum can be characterized by two indices i1 and i2 with i1 < i2 (Note that i1 cannot equal i2 now). Again our original problem can be recast in terms of the value ranges of i1 and i2: given the prefix array and a range [lower, upper], find the total number of range sums lying in that range with 0 <= i1 < i2 <= n, or in a symbolic way T(0, n).

    Again we will break the prefix array into two subarrays, [0, m] and [m+1, n] with m = n/2, and in a similar fashion we will have subproblem T(0,m) if i1 and i2 are both from [0,m]; subproblem T(m+1, n) if both i1 and i2 are from [m+1, n] and a new problem C if i1 from [0, m] while i2 from [m+1, n]:

    T(0, n) = T(0, m) + T(m+1, n) + C

    Now we will aim at linearithmic-like solution for the new problem C: find the total number of range sums lying in the given range with each range sum starting from the first subarray and ending at the second subarray. As you expect, naive solution will run in O(n^2) but we have similar observations here: each range sum can be computed by prefix[i2] - prefix[i1] with i2 from [m+1, n] and i1 from [0, m]. For each index i1, the order doesn't matter in which we compute the range sums for i2 running from m+1 to n. Similar for the other way, for each index i2, the order doesn't matter in which we compute the ranges for i1 running from 0 to m. This allows us to sort the two subarrays. Now suppose we have two sorted subarrays, how do we get the total number of valid range sums? @dietpepsi proposed this two-pointer-like method embedded in merge sort, which is very neat and runs in linear time. You can refer to the original post for more details.

    Before I post the code for this prefix-array based solution, I'd like to mention one point regarding merge sort. Conventionally when we merge two sorted arrays, we use the following routines:

        while (i < array1.length && j < array2.length) {
        	array[k++] = (array1[i] <= array2[j] ? array1[i++] : array2[j++]);
        }
    
        while (i < array1.length) {
        	array[k++] = array1[i++];
        }
    
        while (j < array2.length) {
        	array[k++] = array2[j++];
        }
    

    which is nice for merging purpose. However we also have this modified version of merging:

       while (i < array1.length) {
        	while (j < array2.length && array2[j] < array1[i]) {
       	    array[k++] = array2[j++];
       	}
        	
        	array[k++] = array1[i++];
        }
        
        while (j < array2.length) {
        	array[k++] = array2[j++];
        }
    

    which is particularly useful when we'd like to extract information from the two sorted subarrays, such as summation/difference of pairs with elements from each subarray, or reversion counts during the merging process.

    Anyway, the following code for prefix-array based solution used this version to compute the range counts:

    public int countRangeSumI(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0 || lower > upper) return 0;
    
        long[] prefixArray = new long[nums.length + 1];
    	
        for (int i = 1; i < prefixArray.length; i++) {
    	prefixArray[i] = prefixArray[i - 1] + nums[i - 1];
        }
    	
        return countRangeSumSub(prefixArray, 0, prefixArray.length - 1, lower, upper);
    }
    
    private int countRangeSumSub(long[] prefixArray, int l, int r, int lower, int upper) {
        if (l >= r) return 0;
    	
        int m = l + (r - l) / 2;
    	
        int count = countRangeSumSub(prefixArray, l, m, lower, upper) + countRangeSumSub(prefixArray, m + 1, r, lower, upper);
    	
        long[] mergedArray = new long[r - l + 1];
        int i = l, j = m + 1, k = m + 1, p = 0, q = m + 1;
    	
        while (i <= m) {
    	while (j <= r && prefixArray[j] - prefixArray[i] < lower) j++;
    	while (k <= r && prefixArray[k] - prefixArray[i] <= upper) k++;
    	count += k - j;
    
    	while (q <= r && prefixArray[q] < prefixArray[i]) mergedArray[p++] = prefixArray[q++];
    	mergedArray[p++] = prefixArray[i++];
        }
    	
        while (q <= r) mergedArray[p++] = prefixArray[q++];
    	
        System.arraycopy(mergedArray, 0, prefixArray, l, mergedArray.length);
    	
        return count;
    }
    

  • 27
    F

    Last part is about the solution using binary indexed tree (Fenwick tree). Here is the original post by @lixx2100. The general idea is given in that post but I will try to add more details so we can understand the code better.

    Again we will compute the prefix array (which I will call prefix) of the input array (nums). And each range sum will be characterized by two indices i1 and i2 with 0 <= i1 < i2 <= n. Consider only index i1 now. If for each index i1 running from 0 up to n - 1, we can find all the valid range sums starting at i1 in O(logn) time, then the total runtime will be O(nlogn) since we only need to do that n times. Now how can we obtain all the valid range sums starting at each index i1 with time complexity O(logn)? @lixx2100 mentioned that we can take advantage of data structure such as binary indexed tree but offered no further details except for the code. So I will fill in the gaps here. First here is the code (I used an array called "cand" instead of list):

    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] sum = new long[nums.length + 1];
        long[] cand = new long[3 * sum.length + 1];
        int index = 0;
        cand[index++] = sum[0];
        cand[index++] = lower + sum[0] - 1;
        cand[index++] = upper + sum[0];
    
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
            cand[index++] = sum[i];
            cand[index++] = lower + sum[i] - 1;
            cand[index++] = upper + sum[i];
        }
    
        cand[index] = Long.MIN_VALUE; // avoid getting root of the binary indexed tree when doing binary search
        Arrays.sort(cand);
    
        int[] bit = new int[cand.length];
    
        // build up the binary indexed tree with only elements from the prefix array "sum"
        for (int i = 0; i < sum.length; i++) {
            addValue(bit, Arrays.binarySearch(cand, sum[i]), 1);
        }
    
        int count = 0;
    
        for (int i = 0; i < sum.length; i++) {
            // get rid of visited elements by adding -1 to the corresponding tree nodes
            addValue(bit, Arrays.binarySearch(cand, sum[i]), -1);
    
            // add the total number of valid elements with upper bound (upper + sum[i])
            count += query(bit, Arrays.binarySearch(cand, upper + sum[i]));
    
            // minus the total number of valid elements with lower bound (lower + sum[i] - 1)
            count -= query(bit, Arrays.binarySearch(cand, lower + sum[i] - 1));
        }
    
        return count;
    }
    
    private void addValue(int[] bit, int index, int value) {
        while (index < bit.length) {
            bit[index] += value;
            index += index & -index;
        }
    }
    
    private int query(int[] bit, int index) {
        int sum = 0;
        
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        
        return sum;
    }
    

    The "sum" array is the prefix array. What is the purpose of the array "cand"?

    Remember that for each i1 in the prefix array, we are looking for all the i2's that satisfy:

    lower <= sum[i2] - sum[i1] <= upper (with i2 > i1)

    or equivalently:

    lower + sum[i1] - 1 < sum[i2] <= upper + sum[i1] (with i2 > i1)

    Apparently we'd like to sort the prefix array so we can do binary search. As usual we can get two "insertion points", one for (upper + sum[i1]) and one for (lower + sum[i1] - 1) and the number of valid prefix elements will simply be the indices difference of the two "insertion points", provided there is no restriction on i1 and i2. Unfortunately we do require i1 < i2 to generate a candidate range sum, but sorting the prefix array would break the original index orders and we no longer have guarantee that i1 < i2. Therefore we have to get rid of all those prefix elements between the two "insertion points" with indices up to i1. So it looks like we are in a situation where we want relatively fast operations for both query and updating. Sounds familiar to you? That's where the binary indexed tree comes in, which has O(logn) runtime for both operations.

    To build up the binary indexed tree, we have two strategies: either build the tree against the sorted prefix array or against a new array including the modified lower and upper bounds, (upper + sum[i1]) and (lower + sum[i1] - 1). The code given above takes the second strategy. The upside is that we can take advantage of the built-in binary search functions (java's Arrays.binarySearch() for example); the downside is we need more space.

    Here I'll show how to build up the binary indexed tree corresponding to the new array "cand". I assume you have basic knowledge of binary indexed tree (if not, refer to Fenwick tree). So we have this "bit" array to represent nodes in the binary indexed tree. For each element with index i in the input array ("cand" in this case), we will store a mapped value of the input element at the corresponding node and all its child nodes in the tree.

    Two points here:

    1. The values to store in the tree are not necessarily the elements from the input array itself. You can choose any mapping function you like. (For example, you can choose to return the input elements themselves, or return either 0 or 1 depending on some condition to count the number of elements satisfying that particular condition). The point is that, starting from some given index in the "bit" array, when you traverse toward the root of the tree, the cumulated quantity will correspond to the mapped value. If the mapping function returns the input elements themselves, this cumulated quantity will be the prefix sum of the input array. If the mapping function returns 1 for elements in "cand" that comes from sum[i] and 0 for those from (upper + sum[i1]) or (lower + sum[i1] - 1), then the cumulated quantity will give the total number of elements only from the "sum" array.

    2. For a given index i in the binary index tree, the index of its parent can be obtained by p = i - (i&-i) and its child index can be obtained by c = i + (i&-i). The root of the tree has index 0 and the child index will not go beyond the length of the bit array.

    Eventually we'd like to count the number of valid elements from the prefix array "sum", so our mapping function will assign 1 to elements in "cand" that comes from the "sum" array, and 0 to all other elements. If the assigned value is 0, we don't even bother adding it to the tree nodes. Only when the assigned value is 1 will we add it to the corresponding tree nodes. That's what you see in the code above.

    After the tree is initialized, we'd like to scan the index i1 from 1 up to n. For each i1, we will first get rid of all elements from "sum" with index from 0 up to i1 - 1 (essentially by adding -1 to corresponding nodes in the tree). Then for the upper bound (upper + sum[i1]), we will compute the corresponding index in the "cand" array using binary search and calculate the total number of valid elements up to that index in the binary indexed tree. We then do the same for the lower bound (lower + sum[i1] - 1). The total number of valid elements from the "sum" array will be given by the difference of these two counts. And that's why you see we add the first count then minus the second count in the code. We proceed in this manner until we reach the end of the "sum" array.

    As I mentioned, we can also build the binary indexed tree directly using the prefix array but then you need to come up with your own binary search algorithm instead of the built-in one. Also we do not need to keep a copy of the original prefix array after it is sorted to further save memory space, since the prefix sum array can be computed on the fly as we are scanning the index i1 from 1 to n. If you are interested you can work out those codes very easily.


  • 1

    python implementation :-)

    class Solution(object):
        def countRangeSum(self, nums, lower, upper):
            if not nums:
                return 0
    
            n = len(nums)
            if n == 1:
                return int(lower <= nums[0] <= upper)
    
            mid = n >> 1
            count = sum([
                self.countRangeSum(array, lower, upper)
                for array in [nums[:mid], nums[mid:]]
            ])
    
            suffix, prefix = [0] * (mid + 1), [0] * (n - mid + 1)
            for i in xrange(mid - 1, -1, -1):
                suffix[i] = suffix[i + 1] + nums[i]
    
            for i in xrange(mid, n):
                prefix[i - mid + 1] = prefix[i - mid] + nums[i]
    
            suffix, prefix = suffix[:-1], sorted(prefix[1:])
            count += sum([
                bisect.bisect_right(prefix, upper - s) -
                bisect.bisect_left(prefix, lower - s)
                for s in suffix
            ])
    
        return count
    

  • 0

    python implementation, too :)

    class Solution(object):
        def merge(self, arr1, arr2):
            r, i, j = [], 0, 0
            while i < len(arr1) and j < len(arr2):
                if arr1[i] < arr2[j]:
                    r.append(arr1[i])
                    i += 1
                else:
                    r.append(arr2[j])
                    j += 1
            r += arr1[i:] + arr2[j:]
            return r
    
        def count(self, prefix, start, end, lower, upper):
            if start >= end:
                return 0
    
            mid = start + (end - start + 1 >> 1)
            count = sum([
                self.count(prefix, s, e, lower, upper)
                for s, e in ((start, mid - 1), (mid, end))
            ])
    
            l, r = mid, mid
            for i in xrange(start, mid):
                while l <= end and prefix[l] - prefix[i] < lower:
                    l += 1
                while r <= end and prefix[r] - prefix[i] <= upper:
                    r += 1
                count += r - l
    
            prefix[start:end + 1] = self.merge(
                prefix[start:mid], prefix[mid:end + 1])
    
            return count
    
        def countRangeSum(self, nums, lower, upper):
            n = len(nums)
    
            prefix = [0] * (n + 1)
            for i, v in enumerate(nums, 1):
                prefix[i] = prefix[i - 1] + v
    
            return self.count(prefix, 0, n, lower, upper)
    

  • 0
    A

    Thanks @fun4LeetCode for very good explanations, it's really difficult to understand @dietpepsi algorithm in his native description, although it's still impossible to figure out without some debugging/examples. The algorithm is very neat and fast, though difficult to understand :)


  • 0
    Y

    Thank you for your BIT version, it's very beautiful and helpful! And sorry if I misunderstood you, but just a minor modification to mention. In the second last paragraph, would it be more proper to say "we'd like to scan the index i2 from 1 up to n" instead of "i1" since your equation goes as "lower + sum[i1] - 1 < sum[i2] <= upper + sum[i1] (with i2 > i1)"? In your code we are actually fixing i1 to get the range of i2 :)


  • 0
    F

    Hi yunchen4. Indeed for each i1, we will find all the i2's to form a valid range sum by traversing along the BIT towards the root, but we still need to vary index i1 from 1 up to n in order to find all the possible ranges. So i1 is not fixed. We just pretend it was when dealing with all the ranges starting from i1.


  • 0
    F

    It seems to me that when performing binarySearch over cand, for instance addValue(bit, Arrays.binarySearch(cand, sum[i]), 1), it might be the case that the largest element in cand smaller or equal to sum[i] could be lower+sum[j]-1 or upper+sum[j] (where j may or may not equal to i). Therefore, it seems likely that the final count could be messed up due to the frequency induced by these elements in cand array? Am I missing something? thanks.


  • 0
    F

    Hi faustlin, the binarySearch will return the index of the element being searched (which is sum[i] here) in the cand array. Since we've already added sum[i] into the cand array, it's guaranteed that it will be found and a valid index will be returned.


  • -1
    S

    Arrays.sort() is O(nlogn) so your solution is O(n2)


  • 0
    F

    Hi sindy. According to master's theorem, in this case if the combination part takes O(nlogn) time, the total time complexity will be O(n(logn)^2), not O(n^2).


  • 6
    V

    so far almost all of the leetcode exercises which I don't have a clue at all are from dietpepsi.....


  • 1
    H

    I think the use of BIT is unnecessary.
    So the idea is to find the elements in the prefix sum array whose values are within a range (BTW, this is "value range query" rather than "index range query", which BIT is designed for). After the prefix sum array is sorted, this can already be done in logn time. The only problem left is that when you query range [lower+sum[i1], upper+sum[i1]] for i2 such that sum[i2]-sum[i1] is in [lower,upper], you may get an index i2<i1. So to avoid that, you want to keep the prefix sum array dynamic as well as sorted. i.e. deleting sum[i1] after you query it. This can be done by a balanced tree(TreeSet) easily. Even if you don't like trees, you can still do this deletion on the sorted array without BIT.

    public class Solution {
        private class SumWithIdx
        {
            public long val;
            public int idx;
            public SumWithIdx(long a,int b)
            {
                val = a;
                idx = b;
            }
        }
        private class CompareSum implements Comparator<SumWithIdx>
        {
            public int compare(SumWithIdx a,SumWithIdx b)
            {
                if(a.val<b.val) return -1;
                else if(a.val>b.val) return 1;
                else if(a.idx<b.idx) return -1;
                else return 1;
            }
        }
        public int countRangeSum(int[] nums, int lower, int upper) {
            if(nums==null || nums.length==0) return 0;
            TreeSet<SumWithIdx> prefixSums = new TreeSet<>(new CompareSum());
            prefixSums.add(new SumWithIdx(0L,-1));
            long prefixSumSoFar = 0;
            int cnt = 0;
            for(int i=0;i<nums.length;++i)
            {
                prefixSumSoFar += nums[i];
                SumWithIdx lb = new SumWithIdx(prefixSumSoFar-upper,-2);
                SumWithIdx ub = new SumWithIdx(prefixSumSoFar-lower,nums.length);
                Set<SumWithIdx> x = prefixSums.subSet(lb, true, ub, true);
                cnt += x.size();
                prefixSums.add(new SumWithIdx(prefixSumSoFar,i));
            }
            return cnt;
        }
    }
    

    I am pasting my implementation here but there is another post using TreeMap (for duplicates) that is actually better than this.


  • 0
    N

    @vogelkaka yes, I feel like you. his problem is quite hard to catch.


  • 0
    S

    Java's Arrays.binarySearch will return an arbitrary position among all qualified indices if duplicate elements are contained in the array. However I think the author's intention here is to return the largest qualifying index. Since Java Arrays.binarySearch return the same index for the same array, this bug was not found. However I think we should write our own binarySearch to have this functionality.


  • 0
    F

    @seekerwu70 Hi seekerwu70. As you said, as long as Java's Arrays.binarySearch returns the same index for all the duplicate elements, it doesn't matter whether the index is the largest or not. All the counts will be handled correctly since both adding and removing duplicate elements of the sum array will happen at exactly the same index in the bit array. And of course we can implement our own binary search algorithm to have the whatever effect that is desirable.


  • 0
    Z

    @hao26 Hmm... I have some doubt about this version with TreeSet. Did you pass the TLE? According to the OpenJDK implementation, with the "subset" of a TreeSet, the "size()" is O(n) complexity. So this version would be O(n^2).

    Here is the "size()" implementation I found:
    http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/TreeMap.java#1621


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.