c++ - Is it possible to perform a range addition update, adding a linear function to a max-segment tree? -

i thinking , encountering lot of bugs while trying this. possible?

i believe asking whether can following update: given update b c, want add c elements b.

the problem update on segment tree take o(n * logn) time given n maximum number of elements. however, key idea implementing segment tree suppose range queries , not interested in o(n^2) ranges rather smaller subset of them.

you can enhance range updates using lazy propagation mean update, not update of nodes in segment tree -> update point, not continue futher down tree since not needed.
have updated node k responsible range [10; 30] example. later, "get info" query on [20;40]. obviously, have visit node k, not interested on whole range, rather range [20;30], right child.
have "push" update of node k left child , right child , continue needed.

in general mean when doing update, update until find suitable node(s) interval update, not go further. yields o(logn) time.
then, when quering continue propagating updates down tree when reach node know have saved update later. yields o(logn) time.

some material: lazy propagation on segment trees