Query returns the sum of elements of the array in the interval [firstIndex, leftIndex]. node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively.
(node int, leftNode int, rightNode int, firstIndex int, lastIndex int)
| 45 | // Query returns the sum of elements of the array in the interval [firstIndex, leftIndex]. |
| 46 | // node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively. |
| 47 | func (s *SegmentTree) Query(node int, leftNode int, rightNode int, firstIndex int, lastIndex int) int { |
| 48 | if (firstIndex > lastIndex) || (leftNode > rightNode) { |
| 49 | //outside the interval |
| 50 | return 0 |
| 51 | } |
| 52 | |
| 53 | //propagate lazy tree |
| 54 | s.Propagate(node, leftNode, rightNode) |
| 55 | |
| 56 | if (leftNode >= firstIndex) && (rightNode <= lastIndex) { |
| 57 | //inside the interval |
| 58 | return s.SegmentTree[node] |
| 59 | } |
| 60 | |
| 61 | //get sum of left and right nodes |
| 62 | mid := (leftNode + rightNode) / 2 |
| 63 | |
| 64 | leftNodeSum := s.Query(2*node, leftNode, mid, firstIndex, min.Int(mid, lastIndex)) |
| 65 | rightNodeSum := s.Query(2*node+1, mid+1, rightNode, max.Int(firstIndex, mid+1), lastIndex) |
| 66 | |
| 67 | return leftNodeSum + rightNodeSum |
| 68 | } |
| 69 | |
| 70 | // Update updates the elements of the array in the range [firstIndex, lastIndex] |
| 71 | // with the new value provided and recomputes the sum of different ranges. |