Suffix Balanced Tree

Definition

The order between suffixes is defined by lexicographical order. A Suffix Balanced Tree is a balanced tree that maintains the order of these suffixes, i.e., the suffix balanced tree of a string \(T\) is an ordered set of all suffixes of \(T\). A node in the suffix balanced tree corresponds to a suffix of the original string.

In particular, the in-order traversal of a suffix balanced tree yields the suffix array.

Construction Process

To build a suffix balanced tree for a string \(T\) of length \(n\), consider adding its suffixes in reverse order.

Let \(X\) be the set maintained by the suffix balanced tree, and let \(S\) be the suffix currently being added. Then adding the next suffix means inserting \(\texttt{c}S\) into \(X\) (which can also be understood as the suffix balanced tree maintaining the string \(S\), and the next step is to prepend a character \(\texttt{c}\) to \(S\)). This operation essentially inserts a node into the balanced tree.

Here, we use a balanced tree with expected height \(O(\log n)\), such as a Scapegoat Tree or Treap.

Method 1

During insertion, we compare the order between two suffixes by brute force to decide which subtree to go to. In this way, each insertion requires at most \(O(\log n)\) comparisons, and each comparison takes at most \(O(n)\) time, totaling \(O(n\log n)\).

Since there are \(n\) insertions, the time complexity of this method is bounded by \(O(n^2 \log n)\).

Method 2

Note that the only difference between \(\texttt{c}S\) and \(S\) is the character \(\texttt{c}\), and \(S\) already belongs to \(X\). This can be leveraged to optimize the insertion operation.

Suppose we want to compare the two strings \(\texttt{c}S\) and \(A\), where \(A, S \in X\). During each comparison, we first compare their first characters. If they differ, the order is determined. If they are equal, we only need to compare the order of the strings after removing the first character. Since both strings without their first character already belong to \(X\), we can use the \(O(\log n)\) ranking operation of the balanced tree to complete the comparison. Thus, each insertion takes at most \(O(\log^2 n)\).

Since there are \(n\) insertions, the time complexity of this method is bounded by \(O(n \log^2 n)\).

Method 3

According to Method 2, if we can compare the order between two nodes in the balanced tree in \(O(1)\) time, then the suffix balanced tree can be constructed in \(O(n \log n)\) time.

Let \(val_i\) denote the value of node \(i\). If during the construction of the balanced tree, each node maintains an additional tag \(tag_i\) such that \(tag_i > tag_j \iff val_i > val_j\), then we can determine the order between two nodes in \(O(1)\) based on \(tag_i\).

Let each node in the balanced tree correspond to a real interval, and let the root correspond to \((0, 1)\). For node \(i\), denote its corresponding real interval as \((l, r)\). Then \(tag_i = \frac{l + r}{2}\), its left subtree corresponds to \((l, tag_i)\), and its right subtree corresponds to \((tag_i, r)\). It is easy to verify that \(tag_i\) satisfies the above requirement.

Since we use a balanced tree with expected height \(O(\log n)\), the precision is guaranteed to some extent. In practice, a larger interval can be used, e.g., letting the root correspond to \((0, 10^{18})\).

Method 4

We can first construct the suffix array, and then build the suffix balanced tree based on the suffix array. The complexity bottleneck of this approach lies in the construction of the suffix array or the complexity of inserting \(n\) elements into the balanced tree at once.

Deletion Operation

Suppose the currently added suffix is \(\texttt{c}S\), and the previously added suffix is \(S\). The suffix balanced tree also supports deleting the suffix \(\texttt{c}S\) (which can be understood as the suffix balanced tree maintaining the string \(\texttt{c}S\), and deleting the leading \(\texttt{c}\)).

Similar to the insertion operation, the deletion of \(\texttt{c}S\) can be accomplished using the node deletion operation of the balanced tree.

Advantages of Suffix Balanced Trees

• The idea behind suffix balanced trees is relatively clear and easier to understand compared to other suffix structures like suffix automata. If you can implement a balanced tree, you can implement a suffix balanced tree.
• The complexity of suffix balanced trees does not depend on the size of the character set.
• Suffix balanced trees support deleting a character from the beginning of the string.
• If a persistent balanced tree is used, the suffix balanced tree can also be made persistent.

Example Problems

P3809【Template】Suffix Sorting

A template problem for suffix arrays. After constructing the suffix balanced tree, obtain the suffix array via in-order traversal.

Reference Code (SGT Version)

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

constexpr int N = 1e6 + 5;
constexpr double INF = 1e18;

int n, m, sa[N];
string t;

// SuffixBST(SGT Ver)

// Insert in order, flip the query string when querying
// The suffix starting at i corresponds to node number i
constexpr double alpha = 0.75;
int root;
int sz[N], L[N], R[N];
double tag[N];
int buffer_size, buffer[N];

bool cmp(int x, int y) {
  if (t[x] != t[y]) return t[x] < t[y];
  return tag[x + 1] < tag[y + 1];
}

void init() { root = 0; }

void new_node(int& rt, int p, double lv, double rv) {
  rt = p;
  sz[rt] = 1;
  tag[rt] = (lv + rv) / 2;
  L[rt] = R[rt] = 0;
}

void push_up(int x) {
  if (!x) return;
  sz[x] = sz[L[x]] + 1 + sz[R[x]];
}

bool balance(int rt) { return alpha * sz[rt] > max(sz[L[rt]], sz[R[rt]]); }

void flatten(int rt) {
  if (!rt) return;
  flatten(L[rt]);
  buffer[++buffer_size] = rt;
  flatten(R[rt]);
}

void build(int& rt, int l, int r, double lv, double rv) {
  if (l > r) {
    rt = 0;
    return;
  }
  int mid = (l + r) >> 1;
  double mv = (lv + rv) / 2;

  rt = buffer[mid];
  tag[rt] = mv;
  build(L[rt], l, mid - 1, lv, mv);
  build(R[rt], mid + 1, r, mv, rv);
  push_up(rt);
}

void rebuild(int& rt, double lv, double rv) {
  buffer_size = 0;
  flatten(rt);
  build(rt, 1, buffer_size, lv, rv);
}

void insert(int& rt, int p, double lv, double rv) {
  if (!rt) {
    new_node(rt, p, lv, rv);
    return;
  }

  if (cmp(p, rt))
    insert(L[rt], p, lv, tag[rt]);
  else
    insert(R[rt], p, tag[rt], rv);

  push_up(rt);
  if (!balance(rt)) rebuild(rt, lv, rv);
}

void inorder(int rt) {
  if (!rt) return;
  inorder(L[rt]);
  sa[++m] = rt;
  inorder(R[rt]);
}

void solve(int Case) {
  cin >> t;
  n = t.size();
  t = " " + t;

  init();
  for (int i = n; i >= 1; --i) {
    insert(root, i, 0, INF);
  }

  // Inorder traversal of the suffix BST gives the suffix array
  m = 0;
  inorder(root);

  for (int i = 1; i <= n; ++i) cout << sa[i] << ' ';
  cout << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  solve(1);
  return 0;
}

P6164【Template】Suffix Balanced Tree

Problem Statement

Given an initial string \(s\) and \(q\) operations:

1. Append several characters to the end of the current string.
2. Delete several characters from the end of the current string.
3. Ask how many times the string \(t\) appears as a contiguous substring in the current string?

The problem is forced online. The total length of string changes and the initial length \(\le 8 \times 10^5\), \(q \le 10^5\), and the total length of all queries \(\le 3 \times 10^6\).

For operations 1 and 2, since suffix balanced trees conveniently support prepending and deleting from the beginning, we consider converting tail insertion and tail deletion into head insertion and head deletion. Here, if we maintain the suffix balanced tree of the reversed string of \(s\) instead of \(s\) itself, we can achieve this conversion. Adding and deleting in the balanced tree take \(O(\log n)\) each, so adding or deleting a character takes \(O(\log n)\). Let \(N\) be the total number of characters added or deleted. Then the total time complexity for this part is \(O(N \log n)\).

For operation 3, the number of occurrences of \(t\) equals the number of suffixes that have \(t\) as a prefix. The number of suffixes with \(t\) as a prefix equals the rank of its successor minus the rank of its predecessor. By appending a very large character to \(t\), we can construct a successor of \(t\). By decreasing the last character of \(t\) by 1, we can construct a predecessor of \(t\).

Now, to query the rank of a string \(t\) in the suffix balanced tree, since we cannot guarantee that \(t\) appears in the suffix balanced tree, we can only compare string sizes by brute force each time. A single comparison takes \(O(|t|)\) time, and each query requires at most \(O(\log n)\) comparisons, so the complexity per query is \(O(|t|\log n)\). Let \(L\) be the total length of all query strings. Then the total time complexity for this part is \(O(L \log n)\).

Reference Code (SGT Version)

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

constexpr int N = 8e5 + 5;
constexpr double INF = 1e18;

void decode(string& s, int len, int mask) {
  for (int i = 0; i < len; ++i) {
    mask = (mask * 131 + i) % len;
    swap(s[i], s[mask]);
  }
}

int q, n, na;
string a;
char t[N];

// SuffixBST (SGT Version)

// Insert sequentially, reverse the query string when querying
// The node corresponding to the prefix ending at i has index i
// Note: Lazy deletion cannot be used, as it may break the tree structure
constexpr double alpha = 0.75;
int root;
int sz[N], L[N], R[N];
double tag[N];
int buffer_size, buffer[N];

bool cmp(int x, int y) {
  if (t[x] != t[y]) return t[x] < t[y];
  return tag[x - 1] < tag[y - 1];
}

void init() { root = 0; }

void new_node(int& rt, int p, double lv, double rv) {
  rt = p;
  sz[rt] = 1;
  tag[rt] = (lv + rv) / 2;
  L[rt] = R[rt] = 0;
}

void push_up(int x) {
  if (!x) return;
  sz[x] = sz[L[x]] + 1 + sz[R[x]];
}

bool balance(int rt) { return alpha * sz[rt] > max(sz[L[rt]], sz[R[rt]]); }

void flatten(int rt) {
  if (!rt) return;
  flatten(L[rt]);
  buffer[++buffer_size] = rt;
  flatten(R[rt]);
}

void build(int& rt, int l, int r, double lv, double rv) {
  if (l > r) {
    rt = 0;
    return;
  }
  int mid = (l + r) >> 1;
  double mv = (lv + rv) / 2;

  rt = buffer[mid];
  tag[rt] = mv;
  build(L[rt], l, mid - 1, lv, mv);
  build(R[rt], mid + 1, r, mv, rv);
  push_up(rt);
}

void rebuild(int& rt, double lv, double rv) {
  buffer_size = 0;
  flatten(rt);
  build(rt, 1, buffer_size, lv, rv);
}

void insert(int& rt, int p, double lv, double rv) {
  if (!rt) {
    new_node(rt, p, lv, rv);
    return;
  }

  if (cmp(p, rt))
    insert(L[rt], p, lv, tag[rt]);
  else
    insert(R[rt], p, tag[rt], rv);

  push_up(rt);
  if (!balance(rt)) rebuild(rt, lv, rv);
}

void remove(int& rt, int p, double lv, double rv) {
  if (!rt) return;

  if (rt == p) {
    if (!L[rt] || !R[rt]) {
      rt = (L[rt] | R[rt]);
      rebuild(rt, lv, rv);
    } else {
      // Find the predecessor of rt to replace rt
      int nrt = L[rt];
      while (R[nrt]) {
        nrt = R[nrt];
      }
      remove(L[rt], nrt, lv, tag[rt]);
      L[nrt] = L[rt];
      R[nrt] = R[rt];
      rt = nrt;
      tag[rt] = (lv + rv) / 2;
    }
  } else {
    double mv = (lv + rv) / 2;
    if (cmp(p, rt))
      remove(L[rt], p, lv, mv);
    else
      remove(R[rt], p, mv, rv);
  }

  push_up(rt);
  if (!balance(rt)) rebuild(rt, lv, rv);
}

bool cmp1(const string& s, int len, int p) {
  for (int i = 1; i <= len; ++i, --p) {
    if (s[i] < t[p]) return true;
    if (s[i] > t[p]) return false;
  }
  return false;
}

int query(int rt, const string& s, int len) {
  if (!rt) return 0;
  if (cmp1(s, len, rt))
    return query(L[rt], s, len);
  else
    return sz[L[rt]] + 1 + query(R[rt], s, len);
}

void solve() {
  cin.tie(nullptr)->sync_with_stdio(false);
  n = 0;
  cin >> q;
  init();

  cin >> a;
  na = a.size();
  a = " " + a;
  for (int i = 1; i <= na; ++i) {
    t[++n] = a[i];
    insert(root, n, 0, INF);
  }

  int mask = 0;
  char op[10];
  for (int i = 1; i <= q; ++i) {
    cin >> op;

    // Handle three cases separately

    if (op[0] == 'A') {  // ADD
      cin >> a;
      na = a.size();
      decode(a, na, mask);
      a = " " + a;

      for (int i = 1; i <= na; ++i) {
        t[++n] = a[i];
        insert(root, n, 0, INF);
      }
    } else if (op[0] == 'D') {  // DEL
      int x;
      cin >> x;
      while (x) {
        remove(root, n, 0, INF);
        --n;
        --x;
      }
    } else if (op[0] == 'Q') {  // QUERY
      cin >> a;
      na = a.size();
      decode(a, na, mask);
      a = " " + a;

      reverse(a.begin() + 1, a.begin() + 1 + na);

      a.push_back('Z' + 1);
      int ans = query(root, a, na + 1);

      --a[na];
      ans -= query(root, a, na + 1);

      cout << ans << '\n';
      mask ^= ans;
    }
  }
}

int main() {
  solve();
  return 0;
}

References

• Chen Lijie - "Applications of Weight-Balanced Trees and Suffix Balanced Trees in Informatics Olympiads"

---

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