Range Sum Query - Mutable


  • 0

    Click here to see the full article post


  • 0
    L

    Why is the segment tree implementation correct?
    I could not understand why this segment tree implementation is correct. Given the example listed {2, 4, 5, 7, 8, 9}. The tree array will be {0, 35,29,6,12,17,2,4,5,7,8,9}.

    It does not satisfy the property that for node k with range [i, j], its left child has range [i, i+j/2], and right child has [i+j/2+1, j]. Check the first node in the tree array which is tree[1] = 35. Its left child is tree[2] = 27 and right child is tree[3] = 6. tree[2] is the range sum of [2, 5] while tree[3] is the range sum of [0, 1].

    Am I missing anything here?

    Thanks for any clarification.


  • 0

    @Lin-Yuan Thanks! Below is @elmirap original response to your comment.

    The segmented trie is correct but ranges are not correct. The reader is right.
    The formula k node in range [i..j] , left child of k range-> [i...(i+j)/2], right child of k range[(i+j)/2+1..j] is true only when n is power of two. It is wrong explained in the article.
    This form is not right when n is not power of 2.
    I think that the article should be modified. One way is to say that if k node in range [i..j] , left child of k range-> [i...m], right child of k range[m+1..j] for some j>m >i
    where m is .(i+j)/2 only in case n is power of 2.

    @elmirap had revised the article and the Figure 2. Please let us know if you still see any issue.


  • 0
    A

    I might be wrong but one part of the explanation sounds kinda weird to me. Please correct me if I am wrong. At the step "3 Range Sum Query", you wrote " L is the right child of P ... set L to point to the left of P on the upper level". Shouldn't we set L to the RIGHT of P on the upper level? Since set it to the LEFT direction would expand the range, which would lead to the wrong result? Same problem for "set R to point to the right of P on the upper level".


  • 0

    Dear aiscong,
    Yes, you are right.There is a mistake. I think that ''l" should point to the right of P. I will update the article. Thank you very much for your observation.


  • 0

    @elmirap @aiscong Done, I have just published the revised article. Please let me know if there's still any issue. Thanks!


  • 0
    J

    In the Java code of "Approach #2 (Sqrt decomposition) [Accepted]", b[i / len] += nums[i]. It seems not to match the figure 1 ("Range sum query using SQRT decomposition"). Should it be " b[i / (len-1)] += nums[i]" instead of "b[i / len] += nums[i]" ?
    Thanks


  • 0

    @jiaoliran Yes, really picture is not correct, actually because of rounding errors with sqrt, b[i] will store the sum of sqrt(n) elements only when n is square root of a number, for example n is 4,9,25 and so on. I will modify the picture. Thank you very much for let me know this.


  • 0

    @jiaoliran Thanks for pointing out this issue. I have published the new changes @elmirap made. Please take a look and see if everything looks correct to you now.


  • 0

    Surprised binary indexed tree doesn't show up as a solution. Way easier to code.


  • 0

    @sircodesalotOfTheRound We added reference to it in the article. Thank you for the remind


  • 0
    S

    @elmirap In Approach #3 (Segment tree), the sentence "(11) for the elements from index 0 to index 2. The root (35) being the sum of its children (11);(24)" is not correctly mapping to the figure 2. The child node of root is 6 and 29 instead of 11 and 24


  • 0

    @skysbjdy Thank you very much for the observation. The article is updated. @1337c0d3r please update it. Thank you


  • 0

    @elmirap Thanks, updated.


  • 0
    S

    double l = Math.sqrt(nums.length);
    len = (int) Math.ceil(nums.length/l);

    Why not just write as "len = (int) Math.ceil(Math.sqrt(nums.length)) ?


  • 0
    F

    Thank you very much, I have learnt segment tree from your article.


  • 0

    @fhqplzj I am glad that the article was useful for you!


  • 0
    7

    if the input array has odd length, e.g. 2,4,5,7,8,9,3, the segmented tree structure is messed up I think.


  • 0
    K

    In "Segment Tree" approach, when n is not power of 2, some node's children(section) will be "reversed" just as @Lin Yuan say.I still have some problem with the algorithm's correctness.


  • 0
    X

    It's wrong. In fact, it needs O(4*n) space .


Log in to reply
 

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