Solve range and update queries on big sized arrays initialized with zero.

Правка en2, от ramkanaam, 2015-09-12 13:14:17

Sample problem

We have an imaginary array of size 10^18. And we are given Q queries (Q <= 100000), of the following type

1) increment (l, r, t) : Increase the numbers in the range [l, r] by t.

2) report(l, r) : Report the sum of numbers between [l, r];

How to solve such classes of problems? I have an intuition that we need to bother about indexes, which are used in Queries and no other points. So, I think the solution has to be offline. But, I can't formalize the approach. Can anyone help?.

Теги segment tree, range query, range update

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ramkanaam 2015-09-12 13:14:17 13 Tiny change: 'problem:\n\nWe have ' -
en1 Английский ramkanaam 2015-09-12 13:12:32 578 Initial revision (published)