As we all know, apps like tiktok and instagram destroy peoples attention span. What if we replaced it with an infinite scroll app but for competitive programming? Essentially, we will allow users to submit problems on their own profile with a judging script, (along with a database of problems from major coding platforms). Then you infinitely scroll through problems until you find one you like and can write its code.

The main issue with this if I'm being honest is that there isn't infinite problems, and users can only make so many good problems. But it seems like a fun idea.

Hello everyone! This is the first part of a multi-part blog series dedicated to "mostly useless algorithms". These are algorithms that contain some form of useful use, but are otherwise strictly worse than their peers.

This initial episode shall be dedicated to Square Root and Nth-Root Decomposition.

These are algorithms that implement $$$O(m)$$$ point update, i.e constant point update but $$$O(n^{1/m} * m)$$$ range query. Square Root Decomposition is a degenerate case of this: achieving $$$O(1)$$$ point update, and $$$O(\sqrt{M})$$$ range query. Effectively they are alternatives to Segment and Fenwick tree. With more advanced techniques you could reach $$$O(\log \log n)$$$ queries and updates, or as an upper bound, $$$O(\sqrt{n})$$$ updates and $$$O(\log \log \log \log N)$$$ queries (yes, four logs!)

Now, these algorithms are quite simple, so let us begin with square root decomposition.

Firstly, many problems can be decomposed into smaller "subproblems" that can be merged. For example, if we have the sum of 50 nodes, and we want to get the sum of those along with 20 others, you can simply add their sums together. Square root decomposition uses this philosophy, making $$$\sqrt{n}$$$ intervals of size $$$\sqrt{n}$$$ each. This guarantees you will never have to loop over more than $$$\sqrt{n}$$$ nodes * constant factor, because of this property:

Every query can be composed of 1 "prefix", which the query may or may not completely contain, 1 "suffix", which the query may or may not completely contain, and 0 or more "middle nodes", which are completely contained by the query.

There are a maximum of $$$\sqrt{n}$$$ such "middle nodes", which means you can simply take the aggregate (e.g sum) of these nodes. Then, you have only one prefix/suffix which does not have its own block, Here, we simply loop over the elements that we want: since there are no more than $$$\sqrt{N}$$$ such elements, we never loop over too many.

In order to point update, you simply update the node in the original array, and then its corresponding block. To range update, you can do the same logic as point update: adjust all middle blocks accordingly, adjust prefix and suffix manually, as long as your operation fulfils op(a,z) + op(b,z) + ... = op(aggregate, z).

Now, we have implemented the exact same methods as a segment tree, yet in far simpler, easy to understand methods! Why is this not regularly used, you may wonder?

Well, the time complexity is simply not very good. For $$$N = 2 \times 10^5$$$, $$$N \sqrt{N} \approx 9 \times 10^7$$$, dangerously close to the TLE zone. In simple problems with low constant factor. this is fine. But when constant factor is high, or we need an extra $$$\log n$$$ factor, then we are guaranteed to TLE. Obviously, here you would learn how to use a segment tree (which is effectively square root decomposition if we made every layer 1/2 of the previous).

However, due to the nature of this blog post, we will be looking even further into this!

Your first thought may be to use cube roots, tesseract roots ($$$n^{1/4}$$$) and further. This intuition is correct: one method to expand is by using these. Pick a number (e.g 3 for cube roots). Call this number $$$m$$$. Instead of just one layer, make multiple layers, the first layer has $$$n^{1/m}$$$ blocks of size $$$n^{(n-1)/m}$$$. However, we now have an issue! While summing the middle blocks can be done in $$$n^{1/3}$$$, the prefix and suffix may take up to $$$n^{(n-1)/m}$$$ reads! To fix this, we make $$$n^{2/3}$$$ partial blocks of size $$$n^{1/3}$$$ till you reach $$$n^1$$$. (In other words, split the array into $$$m-1$$$ blocks, each block $$$i$$$ has a size of $$$n^{i/3}$$$.)

Now, to query, you can do it the same method as square root decomposition. Find the "middle" blocks from the top-most layer (the one with the greatest block size), and pick them. Then recurse into the next layer, find the "middle" blocks that have not previously picked, and so on. This achieves an $$$O(n^{1/m})$$$ complexity because you never have to loop over more blocks than that for prefix, suffix and middle combined. Point updates, however are now $$$O(2)$$$ because we must loop over 2 layers. (Range updates now need a more complicated lazy propagation method, similar to that of a segment tree, which is beyond the scope of this blog)

Now the time complexity is far better, $$$N * \text{cube root}(N) * 2$$$: for $$$N = 2 \times 10^5$$$, this achieves $$$\sim 2.6 \times 10^7$$$ ops, leaving you a lot of breathing room. If you pick a larger depth, e.g use $$$n^{1/8}$$$, you can achieve $$$\sim 7.31 \times 10^6$$$ operations ($$$8 N^{9/8}$$$). You may wonder how far you can push it? Well, you can push $$$m$$$ to $$$\log_2 n$$$, which gives... double the nodes per layer! Congrats! We've just reinvented a segment tree! You can also push $$$m$$$ to arbitrary log, e.g $$$\log_{10} m$$$, giving you 10 children per node, (a decary balanced tree?)

Now, why is this useful? Well, the point of the blog is that it isn't. The original (square root decomposition) is used in things like Mo's Algorithm, and is also an extremely simple range update, range query method for beginners to understand. Some of these advantages may too apply to cube root and further decomposition: it does simply devolve into "sum large middle nodes, loop over any partial nodes".

However, this method is part of a larger series of square root decomposition methods, allowing you to achieve $$$\log \log n$$$ updates and queries (by decomposing the square roots into more square roots, then indexing the square root tree with another square root tree), or the promised $$$O(\sqrt{n})$$$ updates and $$$O(\log \log \log \log n)$$$ queries, which is a topic that will, alas, be discussed later, due to the length of this blog.

Implementation of square root decomposition and multi-root decomposition: https://gist.github.com/supastishn/479cfee6c15cdffccc8693befb1ace55

(bad joke, sorry. I couldn't resist.)

/predownloaded/c9/df/c9dfbdd743d518c1b766f8849615e7493da1709e.png

https://codeforces.me/f061c9/1000718703.png

An ambitious goal, but I'll try to do this.

EDIT: I didn't realize rhis would be published on recent actions . I just thought this would appesr on my profile, sorry for the useless post

I'll try solving problems regularly to improvemt skills, and also get faster at solving.