Square-root decomposition

Cut the list into blocks of about √n values and keep one summary per block. Every range is then a few whole blocks plus two short pieces. It is slower than a segment tree, O(√n) instead of O(log n), but it is simple and it bends to questions that trees handle badly.

Blocks

The square root of n, written √n, is the number with √n × √n = n. For example, √100 = 10, because 10 × 10 = 100, and √1,000,000 = 1,000. Cut the list into blocks of b values, about √n, so there are about √n blocks too. For each block keep a summary: its sum, its minimum, or whatever the question needs. Position i is in block i // b.

A range question is answered in three parts:

• the start of the range, inside its first block: read those cells one by one;
• the whole blocks in the middle: read their summaries;
• the end of the range, inside its last block: read those cells one by one.

So a question costs at most 2b + n/b steps. A change to one value updates the value and its block’s summary: O(1) for a sum (add the difference), or O(b) to recompute a minimum.

Choosing the block size

Small blocks make the partial pieces short but give many whole blocks; big blocks do the opposite. The total b + n/b is smallest when the two parts are equal, b = n/b, that is b = √n. Then a question costs O(√n). For a million values that is about 3,000 steps, against about 40 for a segment tree, and a million for a plain scan.

In practice, measure: in Python, reading a block’s cells with a built-in such as sum(a[i:j]) runs in C and is much faster than a loop over summaries, so somewhat larger blocks often win.

Range changes on blocks

Lazy tags (lesson 5) are simple here: one tag per block. To add v to a range, add it to the cells of the two partial pieces (and fix those blocks’ summaries), and add v to the tag of every whole block in between, which also shifts that block’s summary. The true value of a cell is its stored value plus its block’s tag.

class Blocks:                       # range add, range maximum
    def __init__(self, a):
        self.a = list(a)
        self.b = b = max(1, int(len(a) ** 0.5))
        self.tag = [0] * ((len(a) + b - 1) // b)
        self.top = [max(self.a[i:i + b]) for i in range(0, len(a), b)]

    def add(self, l, r, v):             # a[l:r] += v
        b, a = self.b, self.a
        while l < r and l % b:          # the start, cell by cell
            a[l] += v; l += 1
        self._fix((l - 1) // b)
        while l + b <= r:               # whole blocks: just the tag
            self.tag[l // b] += v; l += b
        k = l // b
        while l < r:                    # the end, cell by cell
            a[l] += v; l += 1
        self._fix(k)

    def _fix(self, k):                  # recompute one block's maximum
        if 0 <= k < len(self.top):
            b = self.b
            self.top[k] = max(self.a[k * b:(k + 1) * b])

top[k] stores the largest stored value of block k, without its tag; the true largest is top[k] + tag[k]. A question does the same three parts as before, adding each block’s tag. Practice RNGQ-P6 completes this class.

When to use it

• Odd questions. “How many values in a[l:r] are less than x?”, with changes. Keep each block sorted: a whole block answers with a binary search (BSRC), a partial piece with a scan. A segment tree would need a sorted list at every node.
• Mo’s algorithm. When all the questions are known in advance, sort them by the block of their start, then by their end. Moving the range from one question to the next then adds and removes only about √n cells on average, so questions such as “how many different values are in this range?” cost O((n + q)√n) for q questions.
• A quick first version. It is easy to get right. If it is fast enough, it may be all you need; if not, it is a reliable check for a faster tree.