AIOJ

Introduction

Given a sequence of length n, ${\left\langle a_i\right\rangle}_{i=1}^n$ , and an associative operation $\circ$ (for example, $\gcd,\min,\max,+,\operatorname{and},\operatorname{or},\operatorname{xor}$ are all associative), for each range query $[l,r]$ , we need to compute $a_l\circ a_{l+1}\circ\dotsb\circ a_{r}$ .

A Sqrt Tree can preprocess in $O(n\log\log n)$ time and answer queries in $O(1)$ time.

Explanation

Blocking the sequence

First, we divide the entire sequence into $O(\sqrt{n})$ blocks, each of size $O(\sqrt{n})$ . For each block, we compute:

The prefix range-query results within the block, $P_i$
The suffix range-query results within the block, $S_i$
An additional array $\left\langle B_{i,j}\right\rangle$ that stores the range-query result from block $i$ through block $j$ .

For example, suppose that $\circ$ is addition, $+$ , and the sequence is $\{1,2,3,4,5,6,7,8,9\}$ .

We first divide the sequence into three blocks, obtaining $\{1,2,3\},\{4,5,6\},\{7,8,9\}$ .

The prefix and suffix range-query results for each block are then

\begin{aligned} &P_1=\{1,3,6\},S_1=\{6,5,3\}\\ &P_2=\{4,9,15\},S_2=\{15,11,6\}\\ &P_3=\{7,15,24\},S_3=\{24,17,9\}\\ \end{aligned}

The $B$ array is:

B=\begin{bmatrix} 6 & 21 & 45\\ 0 & 15 & 39\\ 0 & 0 & 24\\ \end{bmatrix}

(For the invalid case $i>j$ , we assume that the answer is 0.)

Clearly, these values can be preprocessed in $O(n)$ time, with the same $O(n)$ space complexity. Once they are ready, we can use them to answer some cross-block queries in $O(1)$ time. However, we still cannot handle queries whose entire interval lies within one block, so we need to process some additional information.

Building a tree

It is natural to recursively construct the structure above within each block to support queries inside a block. Queries for a block of size $1$ can be answered in $O(1)$ time. This gives us a tree in which each node represents an interval of the sequence. Leaf-node intervals have length $1$ or $2$ . A node of size $k$ has $O(\sqrt{k})$ children, so the height of the entire tree is $O(\log\log n)$ . The total length of the intervals on each level is $O(n)$ , so the construction complexity is $O(n\log\log n)$ .

Proof of the tree height

By definition, let $n$ be the number of elements controlled by a node, and let the height of its subtree be $T(n)$ . We can write the recurrence:

T(n)=T(\sqrt n)+1

Substitute $n=2^m$ to obtain

T(2^m)=T(2^{\frac m2})+1

Now define $S(m)=T(2^m)$ . Substitution gives

S(m)=S(\dfrac m2)+1

By the master theorem, $S(m)=O(\log m)$ , and therefore $T(n)=S(\log n)=O(\log\log n)$ .

We can now answer queries in $O(\log\log n)$ time. For a query $[l,r]$ , we only need to quickly find a node $u$ with the smallest possible interval such that $u$ contains $[l,r]$ . Then $[l,r]$ must cross blocks in the block decomposition of $u$ , so its answer can be computed in $O(1)$ time. The total complexity of one query is $O(\log\log n)$ because the tree height is $O(\log\log n)$ . However, this process can still be optimized.

Optimizing query complexity

It is easy to think of binary-searching the height and checking validity in $O(1)$ time. This reduces the complexity to $O(\log\log\log n)$ . However, we can accelerate the process further.

We assume that

The size of every block is an integral power of $2$ ;
The block sizes on the same level are equal.

To achieve this, we append some $0$ elements to the end of the sequence so that its length becomes an integral power of $2$ . Although some blocks may become twice as large as before, they are still of size $O(\sqrt{k})$ , so the preprocessing complexity for the blocks remains $O(n)$ .

We can now easily determine whether a query interval is entirely contained in one block. For an interval $[l,r]$ (zero-indexed), write the endpoints in binary. For example, for $k=4, l=39, r=46$ , the binary representations are

l = 39_{10} = 100111_2, r = 46_{10} = 101110_2

We know that the interval lengths on each level are equal, and that the block sizes are also equal (in the example above, $2^k=2^4=16$ ). These blocks cover the entire sequence, so the first block represents the elements $[0,15]$ (in binary, $[000000_2,001111_2]$ ), while the second block represents the interval $[16,31]$ (in binary, $[010000_2,011111_2]$ ), and so on. We see that the positions of elements in the same block differ only in their last $k$ bits (where $k=4$ in the example). The example's $l,r$ also differ only in their last $k$ bits, so they belong to the same block.

Therefore, we need to check whether the two endpoints of the interval differ only in their last $k$ bits, that is, whether $l\oplus r\le 2^k-1$ . We can then quickly find the layer containing the answer interval:

For each $i\in [1,n]$ , find $i$ , then take its highest-order $1$ bit;
For a query $[l,r]$ , compute the highest-order bit of $l\oplus r$ to quickly determine the layer containing the answer interval.

This lets us answer queries in $O(1)$ time.

Updating elements

Elements can be updated on a Sqrt Tree; both point updates and range updates are supported.

Point updates

Consider a point assignment $a_x=val$ . We want to update the information affected by this operation efficiently.

Naive implementation

First, let us see what happens to a Sqrt Tree after a point update.

Consider a node of length $l$ and its corresponding sequences: $\left\langle P_i\right\rangle,\left\langle S_i\right\rangle,\left\langle B_{i,j}\right\rangle$ . It is easy to see that in each of $\left\langle P_i\right\rangle$ and $\left\langle S_i \right\rangle$ , only $O(\sqrt{l})$ elements change. In $\left\langle B_{i,j}\right\rangle$ , however, $O(l)$ elements change. Thus, $O(l)$ elements are updated in the tree. Therefore, the complexity of a point update on a Sqrt Tree is $O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(n)$ .

Using a Sqrt Tree instead of the B array

The bottleneck of a point update is updating the root node's $\left\langle B_{i,j}\right\rangle$ . Therefore, we try replacing the root node's $\left\langle B_{i,j}\right\rangle$ with another Sqrt Tree, called $index$ . Its role is the same as that of the original two-dimensional array: it stores the answers to queries over entire ranges. Other non-root nodes continue to use $\left\langle B_{i,j}\right\rangle$ . If the root node of a Sqrt Tree has an $index$ structure, we call that Sqrt Tree indexed; if the root node has a $\left\langle B_{i,j}\right\rangle$ structure, we call it unindexed. The $index$ tree itself is unindexed.

We can update the $index$ tree as follows:

In $O(\sqrt{n})$ time, update $\left\langle P_i\right\rangle$ and $\left\langle S_i\right\rangle$ .
Update $index$ . Its length is $O(n)$ , but we only need to update one of its elements (the element representing the changed block), so this step takes $O(\sqrt{n})$ time using the naive algorithm.
Descend into the changed child and update its information in $O(\sqrt{n})$ time using the naive algorithm.

The query complexity remains $O(1)$ because we use the $index$ tree at most once. Therefore, the complexity of a point update is $O(\sqrt{n})$ .

Updating a range

A Sqrt Tree also supports range assignment operations $\operatorname{Update}(l,r,x)$ , which set every number in the interval $[l,r]$ to $x$ . There are two implementation approaches. One updates the information in $O(\sqrt{n}\log\log n)$ time and answers queries in $O(1)$ time; the other updates the information in $O(\sqrt{n})$ time, but increases query time to $O(\log\log n)$ .

We can add lazy tags to a Sqrt Tree just as in a segment tree. There is one difference on a Sqrt Tree: propagating a node's lazy tag may take $O(\sqrt{n})$ time. Therefore, instead of propagating tags while answering a query, we check whether the parent node has a tag and propagate it if it does.

First implementation

In the first implementation, we add lazy tags only to nodes on level $1$ (nodes whose intervals have length $O(\sqrt{n})$ ). When propagating a tag, we update the entire subtree directly, with complexity $O(\sqrt{n}\log\log n)$ . The procedure is as follows:

Consider the nodes on level $1$ . Add a lazy tag to every node completely contained in the update interval;
Two blocks are only partially covered. We directly rebuild these two blocks in $O(\sqrt{n}\log\log n)$ time. If either already has a lazy tag from an earlier update, propagate the tag during the rebuild;
Update the root node's $\left\langle P_i\right\rangle$ and $\left\langle S_i\right\rangle$ in $O(\sqrt{n})$ time;
Rebuild the $index$ tree in $O(\sqrt{n}\log\log n)$ time.

We can now perform range updates efficiently. How do we use lazy tags to answer queries? The procedure is:

If our query is contained within a block with a lazy tag, use the tag to compute the answer;
If our query contains multiple blocks, we only need to consider the answers for the leftmost and rightmost incomplete blocks. The answers for the blocks in between can be queried in the $index$ tree (because the $index$ tree is rebuilt after every update), in $O(1)$ time.

Thus, query complexity remains $O(1)$ .

Second implementation

In this implementation, every node can receive a lazy tag. Therefore, when processing a query, we need to account for lazy tags among its ancestors, making the query complexity $O(\log\log n)$ . The complexity of updating the information becomes lower, however. The procedure is:

For blocks completely contained in the update interval, add a lazy tag to those blocks in $O(\sqrt{n})$ time;
For blocks partially covered by the update interval, update $\left\langle P_i\right\rangle$ and $\left\langle S_i\right\rangle$ in $O(\sqrt{n})$ time (there are only two such blocks);
Update the $index$ tree in $O(\sqrt{n})$ time (using the same update algorithm);
For unindexed subtrees, update their $\left\langle B_{i,j}\right\rangle$ ;
Recursively update the two intervals that are not completely covered.

The time complexity is $O(\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(\sqrt{n})$ .

Implementation

The implementation below builds the tree in $O(n\log\log n)$ time, answers queries in $O(1)$ time, and performs point updates in $O(\sqrt{n})$ time.

SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b);

int log2Up(int n) {
  int res = 0;
  while ((1 << res) < n) {
    res++;
  }
  return res;
}

class SqrtTree {
 private:
  int n, lg, indexSz;
  vector<SqrtTreeItem> v;
  vector<int> clz, layers, onLayer;
  vector<vector<SqrtTreeItem>> pref, suf, between;

  void buildBlock(int layer, int l, int r) {
    pref[layer][l] = v[l];
    for (int i = l + 1; i < r; i++) {
      pref[layer][i] = op(pref[layer][i - 1], v[i]);
    }
    suf[layer][r - 1] = v[r - 1];
    for (int i = r - 2; i >= l; i--) {
      suf[layer][i] = op(v[i], suf[layer][i + 1]);
    }
  }

  void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
    int bSzLog = (layers[layer] + 1) >> 1;
    int bCntLog = layers[layer] >> 1;
    int bSz = 1 << bSzLog;
    int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
    for (int i = 0; i < bCnt; i++) {
      SqrtTreeItem ans;
      for (int j = i; j < bCnt; j++) {
        SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
        ans = (i == j) ? add : op(ans, add);
        between[layer - 1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
      }
    }
  }

  void buildBetweenZero() {
    int bSzLog = (lg + 1) >> 1;
    for (int i = 0; i < indexSz; i++) {
      v[n + i] = suf[0][i << bSzLog];
    }
    build(1, n, n + indexSz, (1 << lg) - n);
  }

  void updateBetweenZero(int bid) {
    int bSzLog = (lg + 1) >> 1;
    v[n + bid] = suf[0][bid << bSzLog];
    update(1, n, n + indexSz, (1 << lg) - n, n + bid);
  }

  void build(int layer, int lBound, int rBound, int betweenOffs) {
    if (layer >= (int)layers.size()) {
      return;
    }
    int bSz = 1 << ((layers[layer] + 1) >> 1);
    for (int l = lBound; l < rBound; l += bSz) {
      int r = min(l + bSz, rBound);
      buildBlock(layer, l, r);
      build(layer + 1, l, r, betweenOffs);
    }
    if (layer == 0) {
      buildBetweenZero();
    } else {
      buildBetween(layer, lBound, rBound, betweenOffs);
    }
  }

  void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
    if (layer >= (int)layers.size()) {
      return;
    }
    int bSzLog = (layers[layer] + 1) >> 1;
    int bSz = 1 << bSzLog;
    int blockIdx = (x - lBound) >> bSzLog;
    int l = lBound + (blockIdx << bSzLog);
    int r = min(l + bSz, rBound);
    buildBlock(layer, l, r);
    if (layer == 0) {
      updateBetweenZero(blockIdx);
    } else {
      buildBetween(layer, lBound, rBound, betweenOffs);
    }
    update(layer + 1, l, r, betweenOffs, x);
  }

  SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
    if (l == r) {
      return v[l];
    }
    if (l + 1 == r) {
      return op(v[l], v[r]);
    }
    int layer = onLayer[clz[(l - base) ^ (r - base)]];
    int bSzLog = (layers[layer] + 1) >> 1;
    int bCntLog = layers[layer] >> 1;
    int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
    int lBlock = ((l - lBound) >> bSzLog) + 1;
    int rBlock = ((r - lBound) >> bSzLog) - 1;
    SqrtTreeItem ans = suf[layer][l];
    if (lBlock <= rBlock) {
      SqrtTreeItem add =
          (layer == 0) ? (query(n + lBlock, n + rBlock, (1 << lg) - n, n))
                       : (between[layer - 1][betweenOffs + lBound +
                                             (lBlock << bCntLog) + rBlock]);
      ans = op(ans, add);
    }
    ans = op(ans, pref[layer][r]);
    return ans;
  }

 public:
  SqrtTreeItem query(int l, int r) { return query(l, r, 0, 0); }

  void update(int x, const SqrtTreeItem &item) {
    v[x] = item;
    update(0, 0, n, 0, x);
  }

  SqrtTree(const vector<SqrtTreeItem> &a)
      : n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg + 1) {
    clz[0] = 0;
    for (int i = 1; i < (int)clz.size(); i++) {
      clz[i] = clz[i >> 1] + 1;
    }
    int tlg = lg;
    while (tlg > 1) {
      onLayer[tlg] = (int)layers.size();
      layers.push_back(tlg);
      tlg = (tlg + 1) >> 1;
    }
    for (int i = lg - 1; i >= 0; i--) {
      onLayer[i] = max(onLayer[i], onLayer[i + 1]);
    }
    int betweenLayers = max(0, (int)layers.size() - 1);
    int bSzLog = (lg + 1) >> 1;
    int bSz = 1 << bSzLog;
    indexSz = (n + bSz - 1) >> bSzLog;
    v.resize(n + indexSz);
    pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
    suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
    between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
    build(0, 0, n, 0);
  }
};

Exercises

CodeChef - SEGPROD

This page is primarily translated from Sqrt Tree - Algorithms for Competitive Programming, under the CC-BY-SA 4.0 license.