frostcloud's blog

Help me to make a data structure
By frostcloud, history, 2 months ago, In English

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?

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

»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 3   Vote: I like it -26 Vote: I do not like it

      From Chat GPT: The merge sort tree is a type of segment tree that merge sorts a randomly-generated array of length $$$2 \cdot 10^5$$$ and element boundary $$$1 \le a_i \le 10^9$$$ after each query. Because of this property, it is very inefficient, and should never be used for non-educational purposes.

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

      https://www.geeksforgeeks.org/merge-sort-tree-for-range-order-statistics/ learn this first.

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

        I found out that I am wrong you can't make range updates using merge sort tree and then count amount of negative numbers on a segment but you can do point updates.

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

          that's why it is said , think before you act.

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

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

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

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

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

      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)

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

        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

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

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

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

      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?

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

        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.

        → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

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

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

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

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    By the way, $$$O(n\sqrt{n}log(n))$$$ does work for subtask 2, which matches your constraints.

    → Reply