Update updates the elements of the array in the range [firstIndex, lastIndex] with the new value provided and recomputes the sum of different ranges. 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, value int)
| 71 | // with the new value provided and recomputes the sum of different ranges. |
| 72 | // node, leftNode and rightNode should always start with 1, 0 and len(Array)-1, respectively. |
| 73 | func (s *SegmentTree) Update(node int, leftNode int, rightNode int, firstIndex int, lastIndex int, value int) { |
| 74 | //propagate lazy tree |
| 75 | s.Propagate(node, leftNode, rightNode) |
| 76 | |
| 77 | if (firstIndex > lastIndex) || (leftNode > rightNode) { |
| 78 | //outside the interval |
| 79 | return |
| 80 | } |
| 81 | |
| 82 | if (leftNode >= firstIndex) && (rightNode <= lastIndex) { |
| 83 | //inside the interval |
| 84 | //accumulate the lazy node value |
| 85 | s.LazyTree[node] += value |
| 86 | s.Propagate(node, leftNode, rightNode) |
| 87 | } else { |
| 88 | //update left and right nodes |
| 89 | mid := (leftNode + rightNode) / 2 |
| 90 | |
| 91 | s.Update(2*node, leftNode, mid, firstIndex, min.Int(mid, lastIndex), value) |
| 92 | s.Update(2*node+1, mid+1, rightNode, max.Int(firstIndex, mid+1), lastIndex, value) |
| 93 | |
| 94 | s.SegmentTree[node] = s.SegmentTree[2*node] + s.SegmentTree[2*node+1] |
| 95 | } |
| 96 | } |
| 97 | |
| 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. |