ramkanaam's blog

Solve range and update queries on big sized arrays initialized with zero.
By ramkanaam, history, 9 years ago, In English

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?.

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

Comments Comments (11)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

  1. read all queries,save them in such a way that you can retrieve the queries after some time.

  2. sort all the indexes appeared in these queries,use std::unique to remove duplicates.

  3. When you are processing these queries,use std::lower_bound to find the "actual" index of these indexes.

  4. Segment tree will do the job. EDIT:My idea is wrong.Refer to Enchom's comment below.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why is this wrong? I'm pretty sure this solves the problem. The difference is that this needs to be offline and spends a little less memory, while lazy logging segment trees also work online.

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

I request all of you, not to write anything now, as this question is in one of the ongoing hackerrank contest.

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

    If you are talking about the 6th problem from the World Cup in Hackerrank — then no, this is not the question. If you're talking about some other problem, then I apologize.

    The problem he asks for is very well studied and has been explained countless times before, it is not something original and there is probably always some ongoing contest using the idea.

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The usual approach for such problems is lazy logging segment trees. In this case (10^18 size) you'd need to use dynamic memory. I believe these trees have been explained many times so a quick google search should give you some ideas. They do work online too :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Generally upto 256MB is allowed in many online judges. So, we can't allocate that much memory.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Did you try to google? If you don't

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

      Please read my comment again and refer to SomeRandomGuy's link. I clearly said you'll need dynamic memory. The tree can be implemented with O(QlogN) memory for array of size N and Q queries.

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

Please don't answer this . This is a question from an ongoing contest.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    I'll just repeat my above comment. This is a simple question that is solved by a structure known for years and problems like these have been given constantly for years.

    If there was some problem from an ongoing contest, for example "find the second-shortest path", and some guy asks how to solve the shortest-path problem, would you say it's from an ongoing contest? Would it be forbidden to speak about Dijkstra until that contest is over?

    → Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone tell the solution now?

→ Reply