# Range Sum Query - Mutable

• 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.

• @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.

• 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".

• 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.

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

• 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

• @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.

• @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.

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

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

• @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

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

• @elmirap Thanks, updated.

• 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)) ?

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

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

• 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.

• 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.

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

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