Sqrt Tree

Introduction

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

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

Explanation

Sequence Blocking

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

\(P_i\): prefix interval queries within the block.
\(S_i\): suffix interval queries within the block.
Maintain an additional array \(\left\langle B_{i,j}\right\rangle\) representing the interval answer from block \(i\) to block \(j\).

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

First, we split the sequence into three blocks: \(\{1,2,3\},\{4,5,6\},\{7,8,9\}\).

Then the prefix and suffix interval answers for each block are:

\[ \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 illegal cases where \(i>j\), we assume the answer is 0.)

Clearly, we can preprocess these values in \(O(n)\) time, with space complexity also \(O(n)\). After preprocessing, we can use them to answer some cross-block queries in \(O(1)\) time. However, we still cannot handle queries entirely within a single block, so we need to process additional information.

Building a Tree

It is natural to think of recursively constructing the above structure within each block to support intra-block queries. For blocks of size \(1\), we can answer queries in \(O(1)\) time. This builds a tree where each node represents an interval of the sequence. Leaf nodes have interval length \(1\) or \(2\). A node of size \(k\) has \(O(\sqrt{k})\) children, so the height of the tree is \(O(\log\log n)\), and the total interval length at each layer is \(O(n)\). Therefore, constructing this tree takes \(O(n\log\log n)\) time.

Proof of Tree Height

By definition, let the subtree height of a node "controlling" \(n\) elements be \(T(n)\). We can write the recurrence:

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

Substitute \(n=2^m\) to get:

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

Define \(S(m)=T(2^m)\), then:

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

By the Master Theorem, \(S(m)=O(\log m)\), so \(T(n)=S(\log n)=O(\log\log n)\).

Now we can answer queries in \(O(\log\log n)\) time. For a query \([l,r]\), we only need to quickly find the node \(u\) with the smallest interval length that contains \([l,r]\), so that \([l,r]\) must span across blocks in \(u\)'s blocked interval, and we can compute the answer in \(O(1)\) time. The overall query complexity is \(O(\log\log n)\) because the tree height is \(O(\log\log n)\). However, we can still optimize this process.

Optimizing Query Complexity

We can think of binary searching the height and then checking validity in \(O(1)\) time. This reduces the complexity to \(O(\log\log\log n)\). But we can further accelerate this process.

We assume:

Each block size is a power of two.
Block sizes are the same within each layer.

To achieve this, we need to pad the sequence with some \(0\) elements at the end so that its length becomes a power of two. Although some blocks may double in size, they are still \(O(\sqrt{k})\), so the preprocessing complexity for blocking remains \(O(n)\).

Now we can easily determine whether a query interval is entirely contained within a single block. For interval \([l,r]\) (0-indexed), write the endpoints in binary. For example, with \(k=4, l=39, r=46\), the binary representation is:

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

We know the interval length at each layer is the same, and the block size is also the same (in this example, \(2^k=2^4=16\)). These blocks completely cover the entire sequence, so the first block represents elements \([0,15]\) (binary \([000000_2,001111_2]\)), the second block represents \([16,31]\) (binary \([010000_2,011111_2]\)), and so on. We observe that elements within the same block differ only in the last \(k\) bits (in this example, \(k=4\)). The example \(l\) and \(r\) also differ only in the last \(k\) bits, so they are in the same block.

Therefore, we need to check whether the two endpoints differ only in the last \(k\) bits, i.e., \(l\oplus r\le 2^k-1\). Thus, we can quickly find the layer where the answer interval lies:

For each \(i\in [1,n]\), find the highest set bit of \(i\).
For a query \([l,r]\), compute the highest set bit of \(l\oplus r\) to quickly determine the layer of the answer interval.

This allows us to answer queries in \(O(1)\) time.

Updating Elements

We can update elements in the Sqrt Tree, supporting both point updates and range updates.

Point Update

Consider a point assignment operation \(a_x=val\). We want to update the information efficiently.

Naive Implementation

First, let's see what happens to the 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 only \(O(\sqrt{l})\) elements change in \(\left\langle P_i\right\rangle\) and \(\left\langle S_i \right\rangle\). In \(\left\langle B_{i,j}\right\rangle\), \(O(l)\) elements change. Therefore, \(O(l)\) elements in the tree are updated. Thus, the complexity of a point update in the Sqrt Tree is \(O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(n)\).

Replacing B Array with Sqrt Tree

Notice that the bottleneck of point updates is updating the root node's \(\left\langle B_{i,j}\right\rangle\). Therefore, we try to replace the root node's \(\left\langle B_{i,j}\right\rangle\) with another Sqrt Tree, called \(index\). Its function is the same as the original 2D array, maintaining the answer for the entire interval query. Other non-root nodes still use \(\left\langle B_{i,j}\right\rangle\) for maintenance. Note: if a Sqrt Tree root has an \(index\) structure, it is called indexed; if a Sqrt Tree root has a \(\left\langle B_{i,j}\right\rangle\) structure, it is called non-indexed. The \(index\) tree itself is non-indexed.

Thus, we can update the \(index\) tree as follows:

Update \(\left\langle P_i\right\rangle\) and \(\left\langle S_i\right\rangle\) in \(O(\sqrt{n})\) time.
Update \(index\), whose length is \(O(n)\), but we only need to update one element (representing the changed block). This step takes \(O(\sqrt{n})\) time (using the naive algorithm).
Enter the child node where the change occurred and update its information using the naive algorithm in \(O(\sqrt{n})\) time.

Note that query complexity remains \(O(1)\) because we use the \(index\) tree at most once. Thus, point update complexity becomes \(O(\sqrt{n})\).

Updating an Interval

Sqrt Tree also supports range assignment operation \(\operatorname{Update}(l,r,x)\), i.e., setting all numbers in interval \([l,r]\) to \(x\). There are two implementations: one takes \(O(\sqrt{n}\log\log n)\) time to update information and \(O(1)\) time to query; the other takes \(O(\sqrt{n})\) time to update but increases query time to \(O(\log\log n)\).

We can use lazy propagation on the Sqrt Tree, similar to segment trees. However, there is a difference in Sqrt Tree: because pushing down a node's lazy tag may cost \(O(\sqrt{n})\), we do not push tags during queries. Instead, we check if a parent node has a tag and push it down if necessary.

First Implementation

In the first implementation, we only apply lazy tags to nodes at the first layer (nodes with interval length \(O(\sqrt{n})\)). When pushing down a tag, we update the entire subtree, costing \(O(\sqrt{n}\log\log n)\). The procedure is as follows:

For nodes at the first layer that are completely covered by the update interval, apply a lazy tag.
For the two blocks only partially covered, rebuild them directly in \(O(\sqrt{n}\log\log n)\) time. If they already have lazy tags from previous updates, push down the tags during rebuilding.
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.

Now we can efficiently perform range updates. How do we answer queries using lazy tags? The procedure is:

If the query is entirely within a block with a lazy tag, compute the answer using the tag.
If the query spans multiple blocks, we only need the answers for the leftmost and rightmost incomplete blocks. The answers for the middle blocks can be queried from the \(index\) tree (since the \(index\) tree is rebuilt after each update) in \(O(1)\) time.

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

Second Implementation

In this implementation, every node can have a lazy tag. Therefore, when processing a query, we need to consider lazy tags from ancestors, increasing query complexity to \(O(\log\log n)\). However, update complexity becomes faster. The procedure is:

For blocks completely covered by the update interval, add lazy tags to them, costing \(O(\sqrt{n})\).
For blocks partially covered, update \(\left\langle P_i\right\rangle\) and \(\left\langle S_i\right\rangle\), costing \(O(\sqrt{n})\) (since only two blocks are modified).
Update the \(index\) tree in \(O(\sqrt{n})\) time (using the same update algorithm).
For non-indexed subtrees, update their \(\left\langle B_{i,j}\right\rangle\).
Recursively update the two intervals not completely covered.

Time complexity is \(O(\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(\sqrt{n})\).

Implementation

The following implementation 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);
  }
};

Practice Problems

CodeChef - SEGPROD

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

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用