segment tree

Second Time
=========================================================================
307  Range Sum Query - Mutable
(1) A naive way is to do range sum query whenever needed, i.e: for loop the number between index i and j and sum all of them together, this takes O(N) time for the range sum query operation.


(2) segment tree

1. Build segment tree

We will use a very effective bottom-up approach to build segment tree. We already know from the above that if some node $p$p holds the sum of $[i \ldots j]$[i…j] range, its left and right children hold the sum for range $[i \ldots \frac{i + j}{2}]$[i…​2​​i+j​​] and $[\frac{i + j}{2} + 1, j]$[​2​​i+j​​+1,j] respectively.
Therefore to find the sum of node $p$p, we need to calculate the sum of its right and left child in advance.
We begin from the leaves, initialize them with input array elements $a[0, 1, \ldots, n-1]$a[0,1,…,n−1]. Then we move upward to the higher level to calculate the parents' sum till we get to the root of the segment tree.

2. Update segment tree

When we update the array at some index $i$i we need to rebuild the segment tree, because there are tree nodes which contain the sum of the modified element. Again we will use a bottom-up approach. We update the leaf node that stores $a[i]$a[i]. From there we will follow the path up to the root updating the value of each parent as a sum of its children values.

3. Range Sum Query

We can find range sum query $[L, R]$[L,R] using segment tree in the following way:
Algorithm hold loop invariant:
$l \le r$l≤r and sum of $[L \ldots l]$[L…l] and $[r \ldots R]$[r…R] has been calculated, where $l$l and $r$r are the left and right boundary of calculated sum. Initially we set $l$l with left leaf $L$L and $r$r with right leaf $R$R. Range $[l, r]$[l,r] shrinks on each iteration till range borders meets after approximately $\log n$logn iterations of the algorithm

• Loop till $l \le$
  • Check if $l$ is right child of its parent $P$
    • $l$l is right child of $P$P. Then $P$ contains sum of range of $l$ and another child which is outside the range $[l, r]$ and we don't need parent $P$ sum. Add $l$ to $sum$ without its parent $P$ and set $l$ to point to the right of $P$ on the upper level.
    • $l$l is not right child of $P$. Then parent $P$ contains sum of range which lies in $[l, r]$. Add $P$ to $sum$ and set $l$ to point to the parent of $P$
  • Check if $r$ is left child of its parent $P$
    • $r$ is left child of $P$. Then $P$ contains sum of range of $r$ and another child which is outside the range $[l, r]$ and we don't need parent $P$ sum. Add $r$ to $sum$ without its parent $P$ and set $r$ to point to the left of $P$ on the upper level.
    • $r$ is not left child of $P$. Then parent $P$ contains sum of range which lies in $[l, r]$[l,r]. Add $P$ to $sum$ and set $r$ to point to the parent of $P$P

Ref: https://leetcode.com/problems/range-sum-query-mutable/solution/#