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.

@LinYuan 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".

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

@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



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.