BLOBVISGOD's blog

By BLOBVISGOD, history, 3 days ago, In English

We have all at some point tried to cheese a problem with square root decomposition, only to be met with a TLE verdict. What if I told you that it is possible to make your solution up to $$$1.5$$$ times faster, while barely changing anything? Although it is not a huge complexity improvement, a $$$1.5\times$$$ difference can often be the difference between AC and TLE if you make sketchy square root complexity solutions, so I think it is still worth sharing.

Let us first look at where the cost of a query of regular square root decomposition comes from. A query can be split up into two parts: the $$$\sqrt{n}$$$-sized blocks that lie fully within the queried interval, and the single elements at the ends of the interval that are not part of any such block. We will for now assume that the cost of traversing a block and the cost of handling a single element at the ends is approximately the same, and then account for this difference later.

There can be almost $$$\sqrt{n}$$$ large blocks to handle, and simultaneously there can be almost $$$\sqrt{n}$$$ single elements to handle at both ends of the queried interval. Thus, in total this costs us $$$\sim3\sqrt{n}$$$ work. We can make this less, by making the blocks smaller, the closer they are to the begin or end of the array:

Since $$$2 \cdot \left(1+2+3+\ldots+\sqrt{n}\right) \approx n$$$, this comes down to having blocks of sizes $$$1,2,3,\ldots$$$ from the ends of the array, inwarwards. In the figure above, we see that if a query goes over the middle of the array, it requires less than $$$2\sqrt{n}$$$ work in total. Similarly, if a query does not go over the middle, $$$2\sqrt{n}$$$ work is required to answer the query. Now let us suppose that handling a block costs $$$g$$$ times more work than handling the single elements at the ends of the query interval. This can for example be the case if you do binary search in the blocks, in which case $$$g \sim \log(n)$$$. Then it turns out that the best size to choose for the $$$i$$$-th block on the left side of the array is approximately $$$gi$$$. In total, there are $$$\sim 2\sqrt{\frac{n}{g}}$$$ blocks, and the middle block has size $$$\sim \sqrt{gn}$$$:

The amount of work done for queries is at most $$$2\sqrt{gn}$$$ instead of $$$3\sqrt{gn}$$$. Hence, choosing block sizes this way results in $$$1.5$$$ times faster queries, even in the unbalanced case. Lastly, I want to mention that updates are just as fast as when using the "regular" square root decomposition: The largest block, which is in the middle of the array, has exactly the same size in this new square root decomposition.

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

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BLOBVISGOD (previous revision, new revision, compare).

»
3 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

would be interesting to see benchmarks across different query distributions too

»
3 days ago, hide # |
 
Vote: I like it +64 Vote: I do not like it

Doesn't work since there are $$$4n$$$ total blocks

»
3 days ago, hide # |
← Rev. 3  
Vote: I like it +16 Vote: I do not like it

There's another nice trick by using prefix and suffix blocks (at the cost of 2x memory). Both queries and updates take exactly $$$O(\sqrt{n})$$$,So making it 3x faster.

  • »
    »
    3 days ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I don't understand what you mean / how it becomes $$$\sqrt{n}$$$ precisely. When calculating a prefix, it is not always possible to efficiently store all intermediate results. For example, if you store a (sorted) list of the values itself. Also, your use of big O notation is a bit strange, as we are counting single instructions, not asymtotics. Can you explain what you mean, exactly?

    • »
      »
      »
      2 days ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      My assumption is that for a query, I know the endpoints ( l ) and ( r ), while for an update, I know the exact position ( x ) where the update is performed.

      Query: I can always take suffix[l], all the complete middle blocks, and prefix[r]. This requires at most $$$\sqrt{n}$$$ moves.

      Update: For the prefix part, I need to update from (x) to the last position of its block. For the suffix part, I need to update from (x) to the starting position of its block. Since the distances from (x) to the beginning and end of its block add up to $$$\sqrt{n}$$$ , the update also requires at most $$$\sqrt{n}$$$ moves.

      Also, you mentioned, "if you store a (sorted) list of the values itself." I didn't quite understand what specific type of problem you're referring to.

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

        That does not nessecarily work. Only if you store $$$O(1)$$$ values inside each prefix & suffix, and we can update them incrementally, which is not guaranteed.

        As per my example, if you store a sorted list of numbers, each update of prefixes / suffixes changes $$$O(\sqrt{n}^2)=O(n)$$$ values. (For example, to binary search when querying)

        Only rarely are those 2 assumptions true and you are not able to do segment tree or d&c.

        • »
          »
          »
          »
          »
          2 days ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it 0 Vote: I do not like it

          If I have to sort the blocks after every update, then obviously my approach will take at list $$$3\sqrt{n}$$$ moves per update, making it clearly worse. Do you have any specific, simple problem where SQRT decomposition + your trick is necessary but my trick wouldn't work? I really want to give it a try.

          • »
            »
            »
            »
            »
            »
            47 hours ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            This problem. Please ignore the timelimit, it is a bit old, and nowadays $$$O(nm)$$$ would probably even pass, but I don't see how prefixes/suffixes would even work here.

            • »
              »
              »
              »
              »
              »
              »
              45 hours ago, hide # ^ |
              ← Rev. 2  
              Vote: I like it +10 Vote: I do not like it

              Thanks, I'll give it a try.

              For this kind of problem, it's obvious my trick won't work at all, though I don't want to use SQRT decomposition either. Using a merge sort tree + ordered set structure should be much easier to code, and the time complexity will be lower too around $$${O}((n+m)\log^2 n)$$$.

              UPDATE: TRYED VJ Source Code

              • »
                »
                »
                »
                »
                »
                »
                »
                20 hours ago, hide # ^ |
                ← Rev. 3  
                Vote: I like it 0 Vote: I do not like it

                SQRT decomposition is 10x faster in practice, and is easier to code (since there are no datastructures) :P

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  19 hours ago, hide # ^ |
                   
                  Vote: I like it +10 Vote: I do not like it

                  Yes but I'd just be a bit careful with this claim in general. Some sqrt-decompositions have to involve data structures either in the block update or block-query merging step. Other times it seems like an obvious sqrt-approach is better than looking for a more complicated log-approach, but the former may be just a less efficient version of the latter — with identical logic aside from block selection. I've ran into this trap several times since I really like going for sqrt-decompositions and when I have a hammer everything looks like a nail. It's always worth a quick check if a log approach would really run into something that sqrt doesn't, but at the same time it's worth starting with thinking about sqrt update/query since it can generalise naturally.

                  Tree sqrt-decompositions are especially tricky in terms of runtime since a (sub)tree can be extremely cache-inefficient and seemingly irrelevant operations like renumbering vertices can have drastic effects on runtime constant.