LashaBukhnikashvili's blog

KQUERY+update=KQUERY2
By LashaBukhnikashvili, 9 years ago, In English

I know you are tired coz of kquery's problems.I am just interested to solve this problem.without update I had on each vertex of segment tree sorted subarray,but now I can't do this with same idea (it was O(n log^2)). also is any idea which solves this problem in O(n log n) ?

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

Comments Comments (29)
| Write comment?
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Disclaimer: There's a good chance this won't quite run in time.

Divide the array into m equal-sized blocks. For each block, keep a binary indexed tree of the elements in that block. Then, for a query, you can make a single query to the BIT (to count elements less than k) for each complete block in the range, and for the two partial blocks on the end, just loop through the elements. Therefore, the query time is O(m * log(10000) + n/m). The update is just updating a single BIT = O(log(10000))

Let m = 50. Then, the total time for 200,000 queries is 200,000 * (50 * log(10000)) + 600), which is about 250 million operations.

I'm hoping there's a way to speed up the queries by slowing down the updates somehow but I can't think of any ways to do that right now.

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

    This is a really beautiful solution!

    At first, I submitted and got TLE, but after playing with the block size, I got accepted.

    Here's my implementation of your great solution: C++ Code

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

    Can't we use the same idea in segment tree? Each node will contain a BIT, which we can use to count elements less than k. Update is similar too.

    The solution is though (but it should be fast enough I guess).

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

      your idea is different,in his idea he divides array into m equal-sized blocks,and you have structore for each node of segment tree.actually,it is also possible to Build BIT, Fenwick Tree , Treap for each node in segment tree(here we can also possible to swap Treap and Segment Tree,and on each node of Treap Build this structures) complexity for each case is O(n log^2 n).

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

        as Diguised say about 2D segment tree ,it's same as Build another segment tree on each node of segment tree and works also in log^2.

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

With updates you can do it in O(n log^2) if you replace sorted arrays with treaps. It is a bit complicated solution, may be it is possible to use something easier.

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

    segment tree+treap it's so hard to implement,it's better to use mkirsche's solution in this way.

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

      why segmenttree+treap harder than sqrtdecomposition+treap??? i thought it is the same...

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

        for me sqrtdecomposition is much more easier than treap to implement.

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

          Oh, sorry, i misread solution in first comment. But now i don't understand why needed BIT if there can be just array.

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

Don't mind, it leads again to log^2.

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

    Can you explain how you do the update with changing only one version?! Don't you need to update all versions with index >= j (If you're updating a[j])?

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

Use 2D segment tree or store a persistent segment tree at each node :D.

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

The first time I AC this problem, I used 2D BIT, which cost so much memory (but it got AC). The main idea of this one is calculating S(x,y) which is number of elements lesser/greater than y in a[1], a[2], ... , a[x].

Later I changed to BIT and sqrt decomposition with the same idea above. You know that a 2D BIT is N 1D BITs in someway. Instead of using N 1D BITs (which is actually a 2D BIT) for N element, I used sqrt(N) 1D BITs which would be a 2D [sqrt(N) x N] BIT. That's all, the remains are just basic sqrt decomposition technique.

Complexity :

O(2*log(sqrt(N)) * log(N) + 2*sqrt(N)) = O(sqrt(N)) per query.

O(log(sqrt(N)) * log(N)) = O((log n)^2) per update operation.

...which is fast enough.

I have no idea how to solve this in O(log n) per operation/query.

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

Hi -

recently I submit this code to this problem; except I get TLE. Solution utilizes 2D segment tree. Anyone can suggest any optimizations that will help it pass?

Thanks in advanced-

Disguised

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

Has anyone been able to get AC in this problem by storing an implicit segment tree in every node of a normal segment tree? I am getting TLE using this idea.

Also how do you solve this problem by 2D segment tree or 2D BIT or by storing a BIT in each node of segment tree? Isn't that going to take too much memory?

N.B.: I have solved this problem using square root decomposition plus BIT. Theoretically the complexity of the query operation for the implicit segment tree idea should be better while that of the update operation of the sqrt idea should be better. But I am interested to know if this problem can be solved using implicit segment trees within time limit.

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

Thanks very much.

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

My O(N lg^2 N) code passes in 1.38s even though the time limit is 1sec lol. My solution: Coordinate Compression + BIT in Segment Tree.

→ Reply