amiralisalimi's blog

Add on interval, Query for number of elements less than given value
By amiralisalimi, 4 years ago, In English

We have an array of numbers and we are supposed to do the following queries on it:

  1. Add number x to all elements on the subarray with indices [ L, R ] of the array.
  2. Query for number of elements less than number x of the whole array.

Note that x is given in each query and is not fixed.

I have a solution with time complexity $$$O(q \cdot log(n) \cdot \sqrt n)$$$ using Square root decomposition (Storing BST for each sqrt block or just sorted subarray in each block) where $$$n$$$ is the size of the array and $$$q$$$ is the number of the queries. However for constraints $$$n, q < 1e5$$$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?

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

»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

MO's algo would be helpful..ig

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

    As there is an add on interval query, I have no idea how to solve this offline.

    → Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Segment Tree Beats is the way to go

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

    I just realized it wouldn't work Never mind :)

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

Can you provide the problem link?

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

Is x fixed? And how large/small can it be?

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

Merge Sort Tree with lazy propagation?

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

    merge sort tree will not work in case of updates

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

      It works with single element updates (with changing sorted arrays to BSTs), but not with interval updates.

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

Use radix sort, then you can solve it in $$$O(n\sqrt{n\log n})$$$ lol

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

    Could you please explain more about your solution? It would be nice if you provide some links to read more and some problems on the algorithm.

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

      You don't need BST, you can store simple sorted array for each block and rebuild it completly when some elements in block are changed. Then, if you manage to make this rebuild in $$$O(blocksize)$$$ (not in $$$O(blocksize \cdot \log{blocksize})$$$, you can set block size to such value that total complexity will became $$$O(\sqrt{n \log{n}})$$$.

      To do this he proposed you to use radix sort, but actually you can achieve it more simple. Just use previous version of sorted array to get separately two sorted sequences of added and non-added elements and then merge this two sequences into one. All this is done by linear time.

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

        Nice trick on merging two sorted arrays instead of rebuilding! But still additional log is needed for the second query.

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

          Yes, but it allows us to set block size equal to $$$\sqrt{n \log n}$$$, so second query is performed in $$$O(\frac{n}{blocksize} \log blocksize) = O(\frac{n}{\sqrt{n \log n}} \log n) = O(\sqrt{n \log n})$$$. And first query is performed in $$$O(blocksize + \frac{n}{blocksize})$$$, which is also $$$O(\sqrt{n \log n})$$$. Without it you can't do this.

          → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

Anyway, I think $$$2$$$ seconds is enough to let the code with the time complexity $$$O(n\sqrt{n\log n})$$$ while $$$n = 10^5$$$ pass on Codeforces. Just have a look at 551E - GukiZ и GukiZiana.

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

The same problem with single position update can be solved by persistent segment trees (check this). I believe it can be modified for an interval update

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

You can make it $$$O((n+q)\sqrt{n})$$$ with fractional cascading but it wasn't really faster than the $$$O((n+q)\sqrt{n\log{n}})$$$ solution in my tests.

There probably isn't a much faster way because a much faster way would mean a much faster (than $$$O(n^3)$$$) way to solve the all-pairs shortest paths problem.

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

    What is the reduction to the all-pairs shortest paths problem?

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

      Here's a reduction from min-plus matrix multiplication, which can be used to solve all-pairs shortest paths:

      Let $$$M$$$ be a number much larger than the elements. The variables $$$i$$$,$$$j$$$ and $$$k$$$ go up to $$$\sqrt{n}$$$.

      Divide the array into $$$\sqrt{n}$$$ blocks of equal size. Set the $$$j$$$th number of the $$$i$$$th block to $$$a_{ij}+jM$$$.

      Do $$$\sqrt{n}$$$ iterations of the following, resetting after each iteration. On the $$$k$$$th iteration, for each $$$i$$$, add $$$b_{ki}$$$ to the $$$i$$$ block. Then, for each $$$j$$$, query $$$Mj+c_{kj}$$$ to determine the number of $$$i$$$ such that $$$a_{ij}+b_{ki}\ge c_{kj}$$$.

      We only care if some $$$i$$$ exists, so we can repeat the entire construction to binary search for all $$$c_{kj}=\min_i(a_{ij}+b_{ki})$$$ in parallel.

      We've used $$$O(n\log{M})$$$ operations to compute the min-plus matrix product of two $$$\sqrt{n}$$$ by $$$\sqrt{n}$$$ matrices.

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

    Can you explain how to do this with fractional cascading? Do you still divide array into blocks of $$$\sqrt n$$$ size?

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

      First divide array into blocks of $$$\sqrt{n}$$$ and keep elements in each block sorted. Then, build something like a segment tree on top of the blocks. Each node will sample every fourth element of its children, so the number of elements per node halves every layer.

      To handle queries, walk down the segment tree to all of its leaves (there are $$$\sqrt{n}$$$ of them) and compute for each node the last element less than $$$x$$$. This can be done in $$$O(1)$$$ per node using the answer from its parent.

      To handle updates, most blocks can get lazily marked. The only ones that can't are the blocks containing the endpoints of the interval and their ancestors in the segment tree. These can be rebuilt in $$$O(\sqrt{n})$$$.

      Here's the code I wrote for this some time ago:

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

        Thanks. This "each node will sample every fourth element of its children" is some next level usage of fractional cascading.

        → Reply