babin's blog

(help) Range updates + range queries on how many occurrences
By babin, history, 6 years ago, In English

Suppose we are given a constant c in the beginning and an array. We have range updates(add a value on a range) and range queries(how many occurrences of c are there in a given range?). Is it possible to effectively perform these queries? I know how to do that for counting the number of minimums/maximums, but I'm not sure if there is a way do that for a constant c given in the beginning. Thanks in advance.

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

»
6 years ago, # |
  Vote: I like it +85 Vote: I do not like it

I don't know of such a data structure, but the funny thing is the constant $$$c$$$ given in the beginning does not make your problem easier.

Consider the general problem where you are given range updates and range queries which can ask how many times number $$$x$$$ occurs where $$$x$$$ can be any number. And consider you have an algorithm $$$A$$$ which solves your "easier" problem, with given $$$c$$$ in the beginning.

But then your algorithm $$$A$$$ can be used to solve this general version of the problem by transforming every query in the general problem:

query l r x

into 2 updates and 1 query in the easier problem:

update l r c-x

query l r

update l r x-c

Thus your best bet is to look for a general algorithm because it's going to be as hard as the algorithm for this problem.

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

    Can you explain your algorithm for general x, on what to query and store??

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

can we solve this problem efficiently problem : given Q queries of type (L,R) find the occurences of each number in the subarray(how many times a number occurs in the subarray L-R).

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

It is easy solvable by sqrt decomposition.

Split the array by sqrt blocks, in each block contains map how many integers with this value in block, plus additional value "add" how much you add to each element in block.

You can get complexity O((n+q)*(sqrt(n)) With hashmap or with map O((n+q)*sqrt(n logn))

I think there is no better solution, but maybe.

P.S. it doesn't matter if it is constant c or not.

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

    can this be solved with mo's if we have offline queries?

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

    I guess $$$O(N^2)$$$ will be faster :)

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

      I don't have this magic ability to write code like you))

      But knowing what you can squeeze to pass, I would believe that you can get AC even with $$$O(N^3)$$$ :)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -36 Vote: I do not like it

      there is no way n^2 would pass n ~ 10^5

      → Reply