Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

atlasworld's blog

Doubt in lazy tree time complexity !

By atlasworld, history, 8 years ago, In English

Suppose we have an array of n = 10^5 elements . 1 index based.

now , we build a segment tree with lazy propogation .

there are large queries , in each query you have to update elements in the range from 1 to n every time . by +x.

will the time complexity be O(n*m*logn) ? ? since everytime our numbers are from minn index to maxxindex.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it +18 Vote: I do not like it

that's incorrect. we can always re-write the arithmetic operation on a segment to (r — l + 1) * x where the segment is represented by [l, r]. Also, it doesn't matter how large your update range is. Only O(logn) segments are processed on each update. This makes your time complexity become O(q * logn) where q is number of queries and n is number of elements in your array.

→ Reply