2. Building a segment tree #
Created Saturday 25 July 2020
- We make an implicit tree, like heap.
- Total elements = 2N-1 check this mathematically.
- We take an array of size 2N, where index 0 is unused, and the 0-N sum is stored at index 1. Children of a node are stored at 2r and 2r+1.
- Build tree - O(N)
- Before building, decide what the segment tree will store, i.e sum, product etc.
