AIOJ

Definition

The order of suffixes is defined lexicographically. A suffix balanced tree is a balanced tree that maintains this suffix order; that is, the suffix balanced tree of a string $T$ is the ordered set of all suffixes of $T$ . Each node in the suffix balanced tree corresponds to one suffix of the original string.

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

Construction

To build the suffix balanced tree for a string $T$ of length $n$ , insert its suffixes into the suffix balanced tree in reverse order.

Let the set maintained by the suffix balanced tree be $X$ , and let the suffix currently being added be $S$ . Adding the next suffix means adding $\mathtt{c}S$ to $X$ (equivalently, if the string maintained by the suffix balanced tree is $S$ , prepend a character $\mathtt{c}$ to $S$ in the next step). This operation is simply an insertion into the balanced tree.

Use a balanced tree with expected height $O(\log n)$ , such as a scapegoat tree or a Treap.

Method 1

During insertion, compare two suffixes by brute force to determine their order, and use that to decide which subtree to insert into. Each insertion performs at most $O(\log n)$ comparisons, and each comparison takes at most $O(n)$ time, for a total of $O(n\log n)$ per construction path.

There are $n$ insertions, so this method has an upper-bound time complexity of $O(n^2 \log n)$ .

Method 2

Observe that $\mathtt{c}S$ and $S$ differ only in $\mathtt{c}$ , and $S$ already belongs to $X$ , so we can use this to optimize insertion.

Suppose we need to compare $\mathtt{c}S$ and $A$ , where $A, S \in X$ . At each comparison, first compare the first characters of the two strings. If they differ, their order is determined; if they are equal, we only need to compare the order of the two strings after removing their first characters. After removing the first character, both strings already belong to $X$ , so we can use the balanced tree's operation for finding a rank in $O(\log n)$ time to complete the comparison. Thus, one insertion takes at most $O(\log^2 n)$ time.

There are $n$ insertions, so this method has an upper-bound time complexity of $O(n \log^2 n)$ .

Method 3

According to Method 2, if we can determine the order of two nodes in the balanced tree in $O(1)$ time, then the suffix balanced tree can be built in $O(n \log n)$ time.

Let $val_i$ denote the value of node $i$ . If, while building the balanced tree, we maintain an additional tag $tag_i$ for each node such that $tag_i > tag_j \iff val_i > val_j$ , then the order of two nodes in the balanced tree can be determined in $O(1)$ time from $tag_i$ tags.

Associate each node in the balanced tree with a real interval, and let the root correspond to $(0, 1)$ . For node $i$ , let its interval be $(l, r)$ , set $tag_i = \frac{l + r}{2}$ , and let its left and right subtrees correspond to $(l, tag_i)$ and $(tag_i, r)$ respectively. It is easy to prove that $tag_i$ has the required property.

Since the balanced tree has expected height $O(\log n)$ , the precision is sufficiently reliable. In an actual implementation, we can also use a larger interval, such as making the root correspond to $(0, 10^{18})$ .

Method 4

One can first construct the suffix array and then construct the suffix balanced tree from the suffix array. The complexity bottleneck is then either the construction of the suffix array or the complexity of inserting $n$ elements into the chosen balanced tree at once.

Deletion

Suppose the suffix currently being added is $\mathtt{c}S$ and the suffix added previously was $S$ . The suffix balanced tree also supports deleting the suffix $\mathtt{c}S$ (equivalently, the string maintained by the suffix balanced tree is $\mathtt{c}S$ , and we remove the initial $\mathtt{c}$ ).

As with insertion, the operation of deleting $\mathtt{c}S$ can be performed using the balanced tree's node-deletion operation.

Advantages of the suffix balanced tree

The idea behind the suffix balanced tree is relatively clear. Compared with suffix structures such as the suffix automaton, it is easier to understand; if you can write a balanced tree, you can write it.
Its complexity does not depend on the size of the character set.
It supports deleting one character from the beginning of a string.
If the balanced tree supports persistence, the suffix balanced tree can also be persistent.

Examples

P3809 - Template Suffix Sorting

This is a template problem for suffix arrays. After building the suffix balanced tree, obtain the suffix array by an in-order traversal.

Reference code for the 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)

// Add in order; reverse the query string when querying
// The suffix beginning at i corresponds to node 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);
  }

  // The in-order traversal of the suffix balanced tree is 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:

Insert several characters at the end of the current string.
Delete several characters from the end of the current string.
Ask how many times the string $t$ occurs as a contiguous substring in the current string.

The problem is forced online. The changing and initial string lengths are at most $\le 8 \times 10^5$ , $q \le 10^5$ , and the total length of all queries is at most $\le 3 \times 10^6$ .

For operations 1 and 2, since a suffix balanced tree conveniently supports inserting and deleting at the front, we can turn insertion and deletion at the end into insertion and deletion at the front. If we maintain the suffix balanced tree of the reverse of $s$ rather than that of $s$ , this conversion is possible. Insertion and deletion in a balanced tree both take $O(\log n)$ time, so adding or deleting one character takes $O(\log n)$ time. Let the total number of added and deleted characters be $N$ ; this part then takes $O(N \log n)$ time.

For operation 3, the number of occurrences of $t$ equals the number of suffixes having $t$ as a prefix, and the number of suffixes prefixed by $t$ , which equals the rank of its successor minus the rank of its predecessor. Appending a very large character to $t$ constructs a successor of $t$ . Decreasing the last character of $t$ by 1 constructs a predecessor of $t$ .

To query the rank of a string $t$ in the suffix balanced tree, we cannot guarantee that $t$ occurs in the tree, so each comparison of string order must be done by brute force. One comparison takes $O(|t|)$ time, and each query performs at most $O(\log n)$ comparisons, so one query takes $O(|t|\log n)$ time. Let the sum of the lengths of all query strings be $L$ ; this part then takes $O(L \log n)$ time in total.

Reference code for the 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 Ver)

// Add in order; reverse the query string when querying
// The prefix ending at i corresponds to node i
// Note: lazy deletion cannot be used, or it may damage 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 the 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 the Informatics Olympiad