hsuyaremo's blog

l-r query

By hsuyaremo, history, 7 years ago, In English

How can i solve a query l-r-x on array where values x,2x,3x,...(r-l+1)x are added to Array[l,l+1,l+2...r] respectively. All ideas are welcomed...

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What do you mean by updations? Isn't that a updation you mentioned?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See here: http://codeforces.net/blog/entry/54103?#comment-381730

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any queries like asking what is the value at some index, or the sum of the elements in a range? Or is it just updating with this kind of updates (and in the end maybe, outputting the whole array)?

If it's the first kind (updates and queries) you could refer to the links other people provided you above using a segment tree as it should be optimal, however if all you need to do is updates then a solution with a total running time of can be done (N, U are the array size and the number of updates, respectively).

→ Reply