c++ - How do I efficiently multiply a range of values of an array with a given number? -

the naive way linearly iterate range , multiply each number in range.

example: array: {1,2,3,4,5,6,7,8,9,10}; multiply index 3 index 8 2. assuming 1 based index.

result array should : {1,2,6,8,10,12,14,16,9,10};

i know binary indexed tree can used 'sum' part. how can efficiently multiply given range number?

if want modify array, can't better naive linear algorithm: have iterate entire range , modify each index accordingly.

if mean like, have update operations described , query operation find sum in range x y, segment tree can so.

for each update operation left, right, value, each node associated range included in [left, right], sum gets multiplied value, update accordingly , stop proceeding recursion. apply intervals not recurse on, instead of updating sum, store in each node how associated interval multiplied by.

when returning recursion, can recompute actual sums according info.

pseudocode:

update(node, left, right, value):   if [left, right] not intersect node.associated_range:     return         if [left, right] included in node.associated_range:     node.multiplications *= value # 1     return    update(node.left, left, right, value)   update(node.right, left, right, value)    node.sum = node.left.sum * node.left.multiplications +              node.right.sum * node.right.multiplications 

basically, each node store sum considering multiplications in child segments. true sum lazily computed during query using information regarding multiplications affected interval.

a sum query performed usual query on segment tree: make sure multiply sums how them or parent intervals multiplied by.

pseudocode:

query(node, multiplications = 1, left, right):   if [left, right] not intersect node.associated_range:     return 0         if [left, right] included in node.associated_range:     return node.sum * multiplications    return query(node.left, multiplications * node.multiplications, left, right) +          query(node.right, multiplications * node.multiplications, left, right) 

the function builds tree left exercise (you can bit better calling update n times).