当想要很快找Sum of Given Range in input. [from index i to index r].

Naive way: Loop from 1 to r to calculate sum of elements in Given Range. O(n) Time.

Better way: 用一个Array 存放sum from start to i. Sum of a Given range can now be calculated.  用两个相减。但是每次update的时候，take O(n). 因为array里可能都有包含你要改的那个元素。

Best: Segment Tree

Perform update and Range Sum in O(logn).   Height = {Logn}

Leaf Nodes are elements of input array

Each Internal node represent some merging of Leaf Nodes.