Propagate propagates the lazy updates to the child nodes
(node int, leftNode int, rightNode int)
| 22 | |
| 23 | // Propagate propagates the lazy updates to the child nodes |
| 24 | func (s *SegmentTree) Propagate(node int, leftNode int, rightNode int) { |
| 25 | if s.LazyTree[node] != emptyLazyNode { |
| 26 | //add lazy node value multiplied by (right-left+1), which represents all interval |
| 27 | //this is the same of adding a value on each node |
| 28 | s.SegmentTree[node] += (rightNode - leftNode + 1) * s.LazyTree[node] |
| 29 | |
| 30 | if leftNode == rightNode { |
| 31 | //leaf node |
| 32 | s.Array[leftNode] += s.LazyTree[node] |
| 33 | } else { |
| 34 | //propagate lazy node value for children nodes |
| 35 | //may propagate multiple times, children nodes should accumulate lazy node value |
| 36 | s.LazyTree[2*node] += s.LazyTree[node] |
| 37 | s.LazyTree[2*node+1] += s.LazyTree[node] |
| 38 | } |
| 39 | |
| 40 | //clear lazy node |
| 41 | s.LazyTree[node] = emptyLazyNode |
| 42 | } |
| 43 | } |
| 44 | |
| 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. |