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

Revision en2, by 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?.

Tags segment tree, range query, range update

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ramkanaam 2015-09-12 13:14:17 13 Tiny change: 'problem:\n\nWe have ' -
en1 English ramkanaam 2015-09-12 13:12:32 578 Initial revision (published)