Sqrt Tree

引入

給你一個長度為 n 的序列 \({\left\langle a_i\right\rangle}_{i=1}^n\)，再給你一個滿足結合律的運算 \(\circ\)（比如 \(\gcd,\min,\max,+,\operatorname{and},\operatorname{or},\operatorname{xor}\) 均滿足結合律），然後對於每一次區間詢問 \([l,r]\)，我們需要計算 \(a_l\circ a_{l+1}\circ\dotsb\circ a_{r}\)。

Sqrt Tree 可以在 \(O(n\log\log n)\) 的時間內預處理，並在 \(O(1)\) 的時間內回答詢問。

解釋

序列分塊

首先我們把整個序列分成 \(O(\sqrt{n})\) 個塊，每一塊的大小為 \(O(\sqrt{n})\)。對於每個塊，我們計算：

1. \(P_i\) 塊內的前綴區間詢問
2. \(S_i\) 塊內的後綴區間詢問
3. 維護一個額外的數組 \(\left\langle B_{i,j}\right\rangle\) 表示第 \(i\) 個塊到第 \(j\) 個塊的區間答案。

舉個例子，假設 \(\circ\) 代表加法運算 \(+\)，序列為 \(\{1,2,3,4,5,6,7,8,9\}\)。

首先我們將序列分成三塊，變成了 \(\{1,2,3\},\{4,5,6\},\{7,8,9\}\)。

那麼每一塊的前綴區間答案和後綴區間答案分別為

\[ \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} \]

\(B\) 數組為：

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

（對於 \(i>j\) 的不合法的情況我們假設答案為 0）

顯然我們可以在 \(O(n)\) 的時間內預處理這些值，空間複雜度同樣是 \(O(n)\) 的。處理好之後，我們可以利用它們在 \(O(1)\) 的時間內回答一些跨塊的詢問。但對於那些整個區間都在一個塊內的詢問我們仍不能處理，因此我們還需要處理一些東西。

構建一棵樹

容易想到我們在每個塊內遞歸地構造上述結構以支持塊內的查詢。對於大小為 \(1\) 的塊我們可以 \(O(1)\) 地回答詢問。這樣我們就建出了一棵樹，每一個結點代表序列的一個區間。葉子結點的區間長度為 \(1\) 或 \(2\)。一個大小為 \(k\) 的結點有 \(O(\sqrt{k})\) 個子節點，於是整棵樹的高度是 \(O(\log\log n)\) 的，每一層的區間總長是 \(O(n)\) 的，因此我們構建這棵樹的複雜度是 \(O(n\log\log n)\) 的。

現在我們可以在 \(O(\log\log n)\) 的時間內回答詢問。對於詢問 \([l,r]\)，我們只需要快速找到一個區間長度最小的結點 \(u\) 使得 \(u\) 能包含 \([l,r]\)，這樣 \([l,r]\) 在 \(u\) 的分塊區間中一定是跨塊的，就可以 \(O(1)\) 地計算答案了。查詢一次的總體複雜度是 \(O(\log\log n)\)，因為樹高是 \(O(\log\log n)\) 的。不過我們仍可以優化這個過程。

優化詢問複雜度

容易想到二分高度，然後可以 \(O(1)\) 判斷是否合法。這樣複雜度就變成了 \(O(\log\log\log n)\)。不過我們仍可以進一步加速這一過程。

我們假設

1. 每一塊的大小都是 \(2\) 的整數冪次；
2. 每一層上的塊大小是相同的。

為此我們需要在序列的末位補充一些 \(0\) 元素，使得它的長度變成 \(2\) 的整數次冪。儘管有些塊可能會變成原來的兩倍大小，但這樣仍是 \(O(\sqrt{k})\) 的，於是預處理分塊的複雜度仍是 \(O(n)\) 的。

現在我們可以輕鬆地確定一個詢問區間是否被整個地包含在一個塊中。對於區間 \([l,r]\)（以 0 為起點），我們把端點寫為二進制形式。舉一個例子，對於 \(k=4, l=39, r=46\)，二進制表示為

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

我們知道每一層的區間長度是相同的，而分塊的大小也是相同的（在上述示例中 \(2^k=2^4=16\)）。這些塊完全覆蓋了整個序列，因此第一塊代表的元素為 \([0,15]\)（二進制表示為 \([000000_2,001111_2]\)），第二個塊代表的元素區間為 \([16,31]\)（二進制表示為 \([010000_2,011111_2]\)），以此類推。我們發現這些在同一個塊內的元素的位置在二進制上只有後 \(k\) 位不同（上述示例中 \(k=4\)）。而示例的 \(l,r\) 也只有後 \(k\) 位不同，因此他們在同一個塊中。

因此我們需要檢查區間兩個端點是否只有後 \(k\) 位不同，即 \(l\oplus r\le 2^k-1\)。因此我們可以快速找到答案區間所在的層：

1. 對於每個 \(i\in [1,n]\)，我們找到 \(i\) 最高位上的 \(1\)；
2. 現在對於一個詢問 \([l,r]\)，我們計算 \(l\oplus r\) 的最高位，這樣就可以快速確定答案區間所在的層。

這樣我們就可以在 \(O(1)\) 的時間內回答詢問啦。

更新元素的過程

我們可以在 Sqrt Tree 上更新元素，單點修改和區間修改都是支持的。

單點修改

考慮一次單點賦值操作 \(a_x=val\)，我們希望高效更新這個操作的信息。

樸素實現

首先我們來看看在做了一次單點修改後 Sqrt Tree 會變成什麼樣子。

考慮一個長度為 \(l\) 的結點以及對應的序列：\(\left\langle P_i\right\rangle,\left\langle S_i\right\rangle,\left\langle B_{i,j}\right\rangle\)。容易發現在 \(\left\langle P_i\right\rangle\) 和 \(\left\langle S_i \right\rangle\) 中都只有 \(O(\sqrt{l})\) 個元素改變。而在 \(\left\langle B_{i,j}\right\rangle\) 中則有 \(O(l)\) 個元素被改變。因此有 \(O(l)\) 個元素在樹上被更新。因此在 Sqrt Tree 上單點修改的複雜度是 \(O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(n)\)。

使用 Sqrt Tree 替代 B 數組

注意到單點更新的瓶頸在於更新根結點的 \(\left\langle B_{i,j}\right\rangle\)。因此我們嘗試用另一個 Sqrt Tree 代替根結點的 \(\left\langle B_{i,j}\right\rangle\)，稱其為 \(index\)。它的作用和原來的二維數組一樣，維護整段詢問的答案。其他非根結點仍然使用 \(\left\langle B_{i,j}\right\rangle\) 維護。注意，如果一個 Sqrt Tree 根結點有 \(index\) 結構，稱其 Sqrt Tree 是 含有索引 的；如果一個 Sqrt Tree 的根結點有 \(\left\langle B_{i,j}\right\rangle\) 結構，稱其是 沒有索引 的。而 \(index\) 這棵樹本身是沒有索引的。

因此我們可以這樣更新 \(index\) 樹：

1. 在 \(O(\sqrt{n})\) 的時間內更新 \(\left\langle P_i\right\rangle\) 和 \(\left\langle S_i\right\rangle\)。
2. 更新 \(index\)，它的長度是 \(O(n)\) 的，但我們只需要更新其中的一個元素（這個元素代表了被改變的塊），這一步的時間複雜度是 \(O(\sqrt{n})\) 的（使用樸素實現的算法）。
3. 進入產生變化的子節點並使用樸素實現的算法在 \(O(\sqrt{n})\) 的時間內更新信息。

注意，查詢的複雜度仍是 \(O(1)\) 的，因為我們最多使用 \(index\) 樹一次。於是單點修改的複雜度就是 \(O(\sqrt{n})\) 的。

更新一個區間

Sqrt Tree 也支持區間覆蓋操作 \(\operatorname{Update}(l,r,x)\)，即把區間 \([l,r]\) 的數全部變成 \(x\)。對此我們有兩種實現方式，其中一種會花費 \(O(\sqrt{n}\log\log n)\) 的複雜度更新信息，\(O(1)\) 的時間查詢；另一種則是 \(O(\sqrt{n})\) 更新信息，但查詢的時間會增加到 \(O(\log\log n)\)。

我們可以像線段樹一樣在 Sqrt Tree 上打懶標記。但是在 Sqrt Tree 上有一點不同。因為下傳一個結點的懶標記，複雜度可能達到 \(O(\sqrt{n})\)，因此我們不是在詢問的時侯下傳標記，而是看父節點是否有標記，如果有標記就把它下傳。

第一種實現

在第一種實現中，我們只會給第 \(1\) 層的結點（結點區間長度為 \(O(\sqrt{n})\)）打懶標記，在下傳標記的時侯直接更新整個子樹，複雜度為 \(O(\sqrt{n}\log\log n)\)。操作過程如下：

1. 考慮第 \(1\) 層上的結點，對於那些被修改區間完全包含的結點，給他們打一個懶標記；

2. 有兩個塊只有部分區間被覆蓋，我們直接在 \(O(\sqrt{n}\log\log n)\) 的時間內 重建 這兩個塊。如果它本身帶有之前修改的懶標記，就在重建的時侯順便下傳標記；

3. 更新根結點的 \(\left\langle P_i\right\rangle\) 和 \(\left\langle S_i\right\rangle\)，時間複雜度 \(O(\sqrt{n})\)；

4. 重建 \(index\) 樹，時間複雜度 \(O(\sqrt{n}\log\log n)\)。

現在我們可以高效完成區間修改了。那麼如何利用懶標記回答詢問？操作如下：

1. 如果我們的詢問被包含在一個有懶標記的塊內，可以利用懶標記計算答案；

2. 如果我們的詢問包含多個塊，那麼我們只需要關心最左邊和最右邊不完整塊的答案。中間的塊的答案可以在 \(index\) 樹中查詢（因為 \(index\) 樹在每次修改完後會重建），複雜度是 \(O(1)\)。

因此詢問的複雜度仍為 \(O(1)\)。

第二種實現

在這種實現中，每一個結點都可以被打上懶標記。因此在處理一個詢問的時侯，我們需要考慮祖先中的懶標記，那麼查詢的複雜度將變成 \(O(\log\log n)\)。不過更新信息的複雜度就會變得更快。操作如下：

1. 被修改區間完全包含的塊，我們把懶標記添加到這些塊上，複雜度 \(O(\sqrt{n})\)；
2. 被修改區間部分覆蓋的塊，更新 \(\left\langle P_i\right\rangle\) 和 \(\left\langle S_i\right\rangle\)，複雜度 \(O(\sqrt{n})\)（因為只有兩個被修改的塊）；
3. 更新 \(index\) 樹，複雜度 \(O(\sqrt{n})\)（使用同樣的更新算法）；
4. 對於沒有索引的子樹更新他們的 \(\left\langle B_{i,j}\right\rangle\)；
5. 遞歸地更新兩個沒有被完全覆蓋的區間。

時間複雜度是 \(O(\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(\sqrt{n})\)。

實現

下面的實現在 \(O(n\log\log n)\) 的時間內建樹，在 \(O(1)\) 的時間內回答詢問，在 \(O(\sqrt{n})\) 的時間內單點修改。

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);
  }
};

習題

CodeChef - SEGPROD

本頁面主要譯自 Sqrt Tree - Algorithms for Competitive Programming，版權協議為 CC-BY-SA 4.0。

---

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