Build builds the SegmentTree by computing the sum of different ranges. node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively.
(node int, left int, right int)
| 98 | // Build builds the SegmentTree by computing the sum of different ranges. |
| 99 | // node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively. |
| 100 | func (s *SegmentTree) Build(node int, left int, right int) { |
| 101 | if left == right { |
| 102 | //leaf node |
| 103 | s.SegmentTree[node] = s.Array[left] |
| 104 | } else { |
| 105 | //get sum of left and right nodes |
| 106 | mid := (left + right) / 2 |
| 107 | |
| 108 | s.Build(2*node, left, mid) |
| 109 | s.Build(2*node+1, mid+1, right) |
| 110 | |
| 111 | s.SegmentTree[node] = s.SegmentTree[2*node] + s.SegmentTree[2*node+1] |
| 112 | } |
| 113 | } |
| 114 | |
| 115 | // NewSegmentTree returns a new instance of a SegmentTree. It takes an input |
| 116 | // array of integers representing Array, initializes and builds the SegmentTree. |