Блог пользователя frostcloud

Help me to make a data structure
Автор frostcloud, история, 3 месяца назад, По-английски

Create a data structure, that can:

  1. Add/subtract a number on a segment;
  2. Count amount of negative numbers on a segment.

How to solve it for $$$O(\sqrt{n})$$$ / $$$O(\log^2{n})$$$ / $$$O(\log{n})$$$ per query?

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think what you are looking for is lazy segment tree + merge sort tree. time complexity is log^2 n per query

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I know about lazy segment tree, but don't know about merge sort tree.

    What is the Merge Sort Tree? How is it implemented? And the main question — how can i update it on some range?

    → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

sqrt decomposition my beloved ($$$O(\sqrt[]{n}log n)$$$ sol so might be a bit slow)

divide the array into $$$\sqrt[]{n}$$$ segments of length $$$\sqrt[]{n}$$$ (and store them twice, one of them is the sorted version)

add/subtract query would take $$$O(\sqrt[]{n} log n)$$$:

for each block store a value which is how much the entire segment is affected by (we'll call it $$$a_i$$$), if the query affects the entire block then just update $$$a_i$$$

if it only affects it partially, then subtract/add those elements and build the sorted array again

for searching negative numbers -> for partial segments just loop through them, for full segments: binary search to find the number of values smaller than $$$-a_i$$$ (also $$$O(\sqrt[]{n}log n)$$$)

obviously it's not the runtime you're looking for but uhm...

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have also thought about it. This is a good idea, but, unfortunately, the complexity is too high.

    Maybe I can do some heavy optimizations, so that it will work for $$$n = queries = 10^5$$$?

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      what is the source of this problem btw? did you come up with it by yourself, or did you reduce some problem on an online judge to this?

      and yes, $$$n\sqrt{n}\text{ log n} \approx 5 \cdot 10^8$$$ operations are probably possible if the code is optimized enough (assuming the time limit isn't too tight)

      → Ответить
      • »
        »
        »
        »
        3 месяца назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        yes, good question. because once I reduced a problem to this problem, and thought n-sqrt-log was too slow. But then after another observation, you can reduce it to the above problem but all values are non-negative; and count zeros instead of negatives

        then you can do lazy seg with min and number of mins

        → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    If you use segments of length sqrt(NlogN) and split+merge when doing updates to a part of a segment, then the operations work in sqrt(NlogN).

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Wow, this makes a lot of sense. How does one go about optimizing block sizes like this? Do you have to just "see" it, or are there some ideas that help?

      → Ответить
      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        Write down the cost of operations.

        If you're able to update/query one block of size N in f(N) and update/query a block partially in g(N) then the cost is (N / X) * f(X) + 2 * g(X). Optimizing that expression we get that X must be O(sqrt(NlogN)) if f(X) = logN and g(X) = X.

        → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can use the lazy segment tree + treap (or any other balanced tree) to solve it in $$$\mathcal O(\log^2 n)$$$ per query. In implementation, you can build a balanced tree for each node in segment tree, and it controls the whole subtree of that node (and as you know, a subtree in segment tree means a interval). Evidently, every node in segment tree will be in $$$\mathcal O(\log n)$$$ balanced trees, so it has a right complexity.

To make the change, you can do it like the simple lazy segment tree. So you can maintain a value $$$add$$$ in segment tree which means "how much this subtree of the node (a interval in fact) add/subtract". When you query, you also just do it like the simple lazy segment tree, but on each node, you should query the rank of $$$-add$$$, because now $$$-add$$$ is $$$0$$$ in fact.

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    pretty sure this fails for similar reasons why merge sort tree fails: when returning back up, how do you merge 2 updated treaps in O(logn)?

    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      emm, you're right. the tag is unable to turn around the hopeless situation of this solution.

      → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There exist a variant of this problem which only deals with subtractions: https://oj.vnoi.info/problem/bedao_m23_e (obviously $$$O(n\sqrt{n}log(n))$$$ does not work here)

→ Ответить