Bỏ qua

Tiền tố & Sai phân

Dẫn nhập

Tiền tố tổng (prefix sum) và hiệu sai phân là những kỹ thuật thường dùng trong lập trình thi đấu, tiền tố tổng dùng để truy vấn tổng đoạn nhanh, còn hiệu sai phân dùng để cập nhật đoạn hiệu quả.

Quy ước

Để thuận tiện, mặc định trong bài này mảng \(\{a_i\}\) đánh chỉ số từ \(1\), và bổ sung \(a_0 = 0\).

Tiền tố tổng

Tiền tố tổng có thể hiểu đơn giản là "tổng \(n\) phần tử đầu của dãy", là một kỹ thuật tiền xử lý quan trọng.

Tiền tố tổng một chiều

Với dãy \(\{a_i\}\) độ dài \(n\), nếu cần truy vấn nhiều lần tổng đoạn \([l,r]\), ta có thể dùng tiền tố tổng:

\[ S_{i} = \sum_{j=1}^i a_j. \]

Có thể tính dần theo công thức truy hồi:

\[ S_0 = 0,~ S_i = S_{i-1} + a_i \]

Khi đó, tổng đoạn \([l,r]\) chỉ cần lấy hiệu:

\[ S([l,r]) = S_r - S_{l-1}. \]

Như vậy, sau \(O(n)\) tiền xử lý, mỗi truy vấn tổng đoạn chỉ còn \(O(1)\).

Cài đặt mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int n;                // Array size.
std::vector<int> a;   // Array. (indexed from 1)
std::vector<int> ps;  // Prefix sum array.

// Calculate prefix sum.
void prefix_sum() {
  ps = a;
  // Or simply:
  // std::partial_sum(a.begin(), a.end(), ps.begin());
  for (int i = 1; i <= n; ++i) {
    ps[i] += ps[i - 1];
  }
}

// Query sum of elements in [l, r].
int query(int l, int r) { return ps[r] - ps[l - 1]; }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
n = 0  # Array size
a = []  # Array (indexed from 1)
ps = []  # Prefix sum array


# Calculate prefix sum
def prefix_sum():
    global ps
    ps = a[:]
    # Or simply:
    # ps = list(itertools.accumulate(a))
    for i in range(1, n + 1):
        ps[i] += ps[i - 1]


# Query sum of elements in [l, r]
def query(l, r):
    return ps[r] - ps[l - 1]

Thư viện chuẩn C++ có hàm tiền tố tổng std::partial_sum trong <numeric>. Từ C++17 còn có std::inclusive_scan cũng trong <numeric>.

Tiền tố tổng đa chiều

Tiền tố tổng một chiều có thể mở rộng lên nhiều chiều. Có hai cách tính tiền tố tổng đa chiều thường gặp.

Dựa trên nguyên lý bao hàm loại trừ

Cách này thường dùng cho tiền tố tổng hai chiều. Cho mảng \(A\) kích thước \(m\times n\), cần tính tiền tố tổng \(S\) cũng kích thước \(m\times n\):

\[ S_{i,j} = \sum_{i'\le i}\sum_{j'\le j}A_{i',j'}. \]

Tương tự một chiều, \(S_{i,j}\) có thể tính từ \(S_{i-1,j}\) hoặc \(S_{i,j-1}\), nhưng nếu cộng cả hai rồi cộng \(A_{i,j}\) sẽ bị tính trùng \(S_{i-1,j-1}\), nên phải trừ đi phần này (nguyên lý bao hàm loại trừ):

\[ S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}. \]

Cứ duyệt \((i,j)\) và tính theo công thức trên.

Ví dụ

Xét ví dụ cụ thể:

二维前缀和示例

\(S\) là tiền tố tổng của ma trận \(A\). Theo định nghĩa, \(S_{3,3}\) là tổng các phần tử trong khung nét đứt. \(S_{3,2}\) là tổng vùng xanh, \(S_{2,3}\) là tổng vùng đỏ, phần giao là \(S_{2,2}\). Nếu cộng \(S_{3,2}\) và \(S_{2,3}\) sẽ bị tính trùng \(S_{2,2}\), nên:

\[ S_{3,3} = A_{3,3} + S_{2,3} + S_{3,2} - S_{2,2} = 5 + 18 + 15 - 9 = 29. \]

Sau khi có tiền tố tổng hai chiều, muốn truy vấn tổng hình chữ nhật từ \((i_1,j_1)\) đến \((i_2,j_2)\):

\[ S_{i_2,j_2} - S_{i_1-1,j_2} - S_{i_2,j_1-1} + S_{i_1-1,j_1-1}. \]

Chỉ mất \(O(1)\) thời gian.

Với hai chiều, độ phức tạp là \(O(mn)\). Nhưng với \(k\) chiều, số lượng các thành phần bao hàm loại trừ tăng theo \(2^k\), nên độ phức tạp là \(O(2^kN)\) với \(N\) là số phần tử, không còn hiệu quả với \(k\) lớn.

洛谷 P1387 Hình vuông lớn nhất

Trong ma trận \(n\times m\) chỉ gồm \(0\) và \(1\), tìm hình vuông lớn nhất không chứa \(0\), in ra cạnh.

Code mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <iostream>
#include <vector>

int n, m;
std::vector<std::vector<int>> a, ps;  // (n + 1) x (m + 1).

// Calculate the prefix sum of 2-d array.
void prefix_sum() {
  ps = a;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
}

// Find the sum of elements in submatrix [x1, y1] to [x2, y2].
int query(int x1, int y1, int x2, int y2) {
  return ps[x2][y2] - ps[x1 - 1][y2] - ps[x2][y1 - 1] + ps[x1 - 1][y1 - 1];
}

int main() {
  std::cin >> n >> m;
  a.assign(n + 1, std::vector<int>(m + 1));

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) std::cin >> a[i][j];

  prefix_sum();

  int ans = 0;
  for (int l = 1; l <= std::min(n, m); ++l)
    for (int i = l; i <= n; i++)
      for (int j = l; j <= m; j++)
        if (query(i - l + 1, j - l + 1, i, j) == l * l) ans = std::max(ans, l);

  std::cout << ans << std::endl;
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
n, m = 0, 0
a = []  # (n+1) x (m+1)
ps = []  # prefix sum array


# Calculate the prefix sum of 2D array.
def prefix_sum():
    global ps
    ps = [row[:] for row in a]  # Deep copy of a
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1]


# Find the sum of elements in submatrix [x1, y1] to [x2, y2].
def query(x1, y1, x2, y2):
    return ps[x2][y2] - ps[x1 - 1][y2] - ps[x2][y1 - 1] + ps[x1 - 1][y1 - 1]


if __name__ == "__main__":
    n, m = map(int, input().split())

    # Initialize with zero padding for 1-based indexing
    a = [[0] * (m + 1)]
    for _ in range(n):
        row = list(map(int, input().split()))
        a.append([0] + row)

    prefix_sum()
    ans = 0

    for l in range(1, min(n, m) + 1):
        for i in range(l, n + 1):
            for j in range(l, m + 1):
                if query(i - l + 1, j - l + 1, i, j) == l * l:
                    ans = max(ans, l)

    print(ans)

Tiền tố tổng từng chiều

Với mảng \(k\) chiều \(A\) kích thước \(N\), cũng có thể tính tiền tố tổng \(S\) như sau:

\[ S_{i_1,\cdots,i_k} = \sum_{i'_1\le i_1}\cdots\sum_{i'_k\le i_k} A_{i'_1,\cdots,i'_k}. \]

Tức là, mỗi lần chỉ tính tiền tố tổng theo một chiều, cố định các chiều còn lại, lặp lại cho \(k\) chiều. Độ phức tạp \(O(kN)\), thường chấp nhận được.

Code mẫu tiền tố tổng 3 chiều 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int N1, N2, N3;
std::vector<std::vector<std::vector<int>>> a,
    ps;  // (N1 + 1) x (N2 + 1) x (N3 + 1).

// Calculate prefix sum of 3d array.
void prefix_sum() {
  ps = a;

  // Prefix-sum for 3rd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j][k - 1];

  // Prefix-sum for 2nd dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i][j - 1][k];

  // Prefix-sum for 1st dimension.
  for (int i = 1; i <= N1; ++i)
    for (int j = 1; j <= N2; ++j)
      for (int k = 1; k <= N3; ++k) ps[i][j][k] += ps[i - 1][j][k];
}

Trường hợp đặc biệt: DP tổng trên tập con (SOS DP)

Khi \(k\) lớn, thường gặp trong bài toán tổng trên tập con (sum over subsets, SOS). Đây là trường hợp đặc biệt của tiền tố tổng nhiều chiều.

Bài toán: Cho hàm \(f\) trên tập các tập con của \(n\) phần tử, tính hàm \(g\):

\[ g(S) = \sum_{T\subseteq S}f(T). \]

Tức là \(g(S)\) là tổng \(f(T)\) trên mọi tập con \(T\) của \(S\).

Có thể coi \(f\) là mảng \(n\) chiều, mỗi chiều chỉ nhận \(0\) hoặc \(1\). Quan hệ tập con tương ứng với quan hệ chỉ số: \(T\subseteq S \iff \forall i(t_i \le s_i)\). Vậy tổng trên tập con chính là tiền tố tổng nhiều chiều.

Có thể dùng cách trên để tính, độ phức tạp \(O(n2^n)\).

Code mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
int n;
std::vector<int> a, ps;  // length = 1 << n.

void sum_of_subsets() {
  ps = a;
  // Loop over dimensions.
  for (int i = 0; i < n; ++i) {
    // Loop over i-th dimension.
    for (int st = 0; st < (1 << n); ++st) {
      // This condition implies that i-th dimension is 1.
      if ((st >> i) & 1) {
        // ps[... 1 ...] += ps[... 0 ...]. (i-th dimension)
        ps[st] += ps[st ^ (1 << i)];
      }
    }
  }
}

Phép nghịch đảo của tổng trên tập con cần dùng nguyên lý bao hàm loại trừ. Đây cũng là bước cần thiết trong biến đổi Möbius nhanh.

Tiền tố tổng trên cây

Tiền tố tổng một chiều còn có thể mở rộng lên cây có gốc (gốc là \(1\)). Sau khi tiền xử lý, có thể truy vấn nhanh tổng trọng số trên đường đi.

Trường hợp trọng số trên nút

Giả sử mỗi nút \(x\) có trọng số \(a_x\). Có thể tính tiền tố tổng \(S_x\) từ gốc đến \(x\) theo:

\[ S_1 = a_1,~ S_{x} = S_{\operatorname{fa}(x)} + a_x \]

Sau khi tiền xử lý, tổng trọng số trên đường đi từ \(x\) đến \(y\) là:

\[ S_x + S_y - S_{\operatorname{lca}(x, y)} - S_{\operatorname{fa}(\operatorname{lca}(x, y))} \]

với \(\operatorname{lca}(x, y)\) là tổ tiên chung gần nhất.

Trường hợp trọng số trên cạnh

Trọng số trên cạnh có thể chuyển về trọng số trên nút. Với mỗi nút \(x\neq 1\), gọi \(\operatorname{edge}(x)\) là cạnh nối \(x\) với cha \(\operatorname{fa}(x)\). Gán trọng số cạnh vào nút xa gốc hơn, gốc nhận \(0\). Khi đó, dùng công thức trên để tính tiền tố tổng cạnh.

Tổng trọng số trên đường đi từ \(x\) đến \(y\) là:

\[ S_x + S_y - 2S_{\operatorname{lca}(x, y)} \]

Khác với trường hợp trọng số trên nút, không tính trọng số tại \(\operatorname{lca}(x, y)\).

Tổng trọng số dưới cây con

Khác với mảng, trên cây hướng, tổng tiền tố từ dưới lên (từ lá lên gốc) và từ trên xuống (từ gốc xuống lá) cho kết quả khác nhau. Thông thường, "tiền tố tổng trên cây" là từ gốc xuống. Để phân biệt, gọi tổng từ dưới lên là tổng dưới cây con.

Tổng trọng số dưới cây con gốc \(x\) là:

\[ T_x = \sum_{y\in\operatorname{desc}(x)} a_x. \]

với \(\operatorname{desc}(x)\) là tập các con cháu (kể cả \(x\)). Tổng dưới cây con không dùng để truy vấn nhanh tổng đường đi, nhưng lại hữu ích cho phần hiệu sai phân trên cây.

Hiệu sai phân

Hiệu sai phân là phép toán ngược với tiền tố tổng. Trong thi đấu, thường dùng hiệu sai phân để thực hiện nhiều phép cộng đoạn, sau đó dùng tiền tố tổng để khôi phục giá trị từng phần tử. Lưu ý phải thực hiện cập nhật trước khi truy vấn.

Nếu cần hỗ trợ cập nhật và truy vấn lẫn nhau, hãy dùng Fenwick tree, nhưng ý tưởng vẫn giống nhau.

Hiệu sai phân một chiều

Với dãy \(\{a_i\}\), hiệu sai phân \(\{D_i\}\) là:

\[ D_i = a_i - a_{i-1},~ a_0 = 0. \]

Thư viện chuẩn C++ có hàm std::adjacent_difference trong <numeric>.

Quan hệ giữa tiền tố tổng và hiệu sai phân:

Tính chất

Nếu \(\{D_i\}\) là hiệu sai phân của \(\{a_i\}\), thì:

  • \(\{a_i\}\) là tiền tố tổng của \(\{D_i\}\):

    \[ a_i = \sum_{j=1}^i D_i. \]

  • Tiền tố tổng của \(\{a_i\}\) là:

    \[ S_i = \sum_{j=1}^i\sum_{k=1}^jD_k = \sum_{j=1}^i(i-j+1)D_j. \]

Hiệu sai phân thường dùng để thực hiện nhiều phép cộng đoạn, sau đó truy vấn giá trị từng phần tử.

Giả sử cần cộng \(v\) cho tất cả \(a_i\) với \(l\leq i\leq r\), chỉ cần:

\[ D_{l} \gets D_{l} + v,~ D_{r+1}\gets D_{r+1} - v. \]

Sau khi cập nhật xong, dùng tiền tố tổng để khôi phục dãy \(a_i\). Mỗi lần cập nhật \(O(1)\), truy vấn sau khi tiền xử lý là \(O(1)\).

Code mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int n;
std::vector<int> diff, a;

// Add v to each element in [l, r].
void add(int l, int r, int v) {
  diff[l] += v;
  if (r < n) diff[r + 1] -= v;
}

// Execute this after all modifications and before all queries.
void prefix_sum() {
  for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + diff[i];
}

Hiệu sai phân đa chiều

Hiệu sai phân cũng mở rộng được cho nhiều chiều, là phép toán ngược với tiền tố tổng đa chiều. Có thể dùng nguyên lý bao hàm loại trừ, ví dụ hiệu sai phân hai chiều:

\[ D_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}. \]

Tuy nhiên, cách hiệu quả hơn là thực hiện hiệu sai phân từng chiều.

Hiệu sai phân hai chiều thường dùng để thực hiện nhiều phép cộng hình chữ nhật. Để cộng \(v\) cho mọi phần tử trong hình chữ nhật từ \((x_1,y_1)\) đến \((x_2,y_2)\), chỉ cần:

\[ \begin{aligned} D_{x_1,y_1} &\gets D_{x_1,y_1} + v, \\ D_{x_1,y_2+1} &\gets D_{x_1,y_2+1} - v,\\ D_{x_2+1,y_1} &\gets D_{x_2+1,y_1} - v,\\ D_{x_2+1,y_2+1} &\gets D_{x_2+1,y_2+1} + v. \end{aligned} \]

Sau khi cập nhật xong, chỉ cần tính tiền tố tổng hai chiều để khôi phục mảng.

Code mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
int n, m;
std::vector<std::vector<int>> diff, a;

// Add v to each element from [x1, y1] to [x2, y2].
void add(int x1, int y1, int x2, int y2, int v) {
  diff[x1][y1] += v;
  if (x2 < n) diff[x2 + 1][y1] -= v;
  if (y2 < m) diff[x1][y2 + 1] -= v;
  if (x2 < n && y2 < m) diff[x2 + 1][y2 + 1] += v;
}

// Execute this after all modifications and before all queries.
void prefix_sum() {
  a = diff;

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) a[i][j] += a[i - 1][j];

  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) a[i][j] += a[i][j - 1];
}

Tương tự, với \(k>2\) chiều cũng làm được, nhưng mỗi lần cập nhật tốn \(O(2^k)\).

Hiệu sai phân trên cây

Hiệu sai phân cũng mở rộng lên cây có gốc, dùng để thực hiện phép cộng đoạn trên đường đi. Tùy vào việc lưu thông tin ở nút hay cạnh, có hai loại: hiệu sai phân trên nút và hiệu sai phân trên cạnh.

Khác với tiền tố tổng trên cây, hiệu sai phân thường dùng để cập nhật xong rồi tính tổng dưới cây con để truy vấn.

Hiệu sai phân trên nút

Để cộng \(v\) cho tất cả các nút trên đường đi từ \(x\) đến \(y\), chỉ cần:

\[ \begin{aligned} D_x &\gets D_x + v, \\ D_{\operatorname{lca}(x, y)} &\gets D_{\operatorname{lca}(x, y)} - v,\\ D_y &\gets D_y + v, \\ D_{\operatorname{fa}(\operatorname{lca}(x, y))} &\gets D_{\operatorname{fa}(\operatorname{lca}(x, y))} - v. \end{aligned} \]

Sau khi cập nhật xong, tính tổng dưới cây con để lấy giá trị từng nút.

Ví dụ

Khi cộng đoạn trên đường đi từ \(S\) đến \(T\), hai dòng đầu là cộng trên đoạn xanh, hai dòng sau là cộng trên đoạn đỏ:

Tính tổng dưới cây con từ dưới lên là đúng.

Hiệu sai phân trên cạnh

Để cộng \(v\) cho tất cả các cạnh trên đường đi từ \(x\) đến \(y\), chỉ cần:

\[ \begin{aligned} D_x &\gets D_x + v, \\ D_y &\gets D_y + v, \\ D_{\operatorname{lca}(x, y)} &\gets D_{\operatorname{lca}(x, y)} - 2v. \end{aligned} \]

Sau khi cập nhật xong, tính tổng dưới cây con để lấy giá trị từng cạnh.

Ví dụ

Như hình, hiệu sai phân trên cạnh dùng để cộng đoạn trên các cạnh màu đỏ.

Vì khó cộng trực tiếp trên cạnh, nên chuyển về cộng trên nút liền kề. So sánh với hiệu sai phân trên nút sẽ hiểu công thức này.

Bài tập ví dụ

洛谷 3128 Lưu lượng lớn nhất

FJ lắp \(N(2 \le N \le 50,000)\) đường ống nối \(N-1\) kho, đánh số \(1\) đến \(N\), tất cả đều liên thông.

Có \(K(1 \le K \le 100,000)\) tuyến vận chuyển sữa, tuyến \(i\) từ kho \(s_i\) đến \(t_i\). Mỗi tuyến làm tăng áp lực lên các kho trên đường đi thêm \(1\). Hỏi kho nào chịu áp lực lớn nhất.

Hướng dẫn giải

Cần đếm số lần mỗi nút bị đi qua, dùng hiệu sai phân trên cây, mỗi lần cộng \(1\) trên đường đi. Dùng phương pháp bội số hóa để tính LCA, cuối cùng duyệt DFS toàn bộ cây, khi quay lui cộng dồn hiệu sai phân để lấy đáp án.

Code mẫu 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <iostream>
using namespace std;

constexpr int MAXN = 50010;

struct node {
  int to, next;
} edge[MAXN << 1];

int fa[MAXN][30], head[MAXN << 1];
int power[MAXN];
int depth[MAXN], lg[MAXN];
int n, k, ans = 0, tot = 0;

void add(int x, int y) {  // 加边
  edge[++tot].to = y;
  edge[tot].next = head[x];
  head[x] = tot;
}

void dfs(int now, int father) {  // dfs求最大压力
  fa[now][0] = father;
  depth[now] = depth[father] + 1;
  for (int i = 1; i <= lg[depth[now]]; ++i)
    fa[now][i] = fa[fa[now][i - 1]][i - 1];
  for (int i = head[now]; i; i = edge[i].next)
    if (edge[i].to != father) dfs(edge[i].to, now);
}

int lca(int x, int y) {  // 求LCA，最近公共祖先
  if (depth[x] < depth[y]) swap(x, y);
  while (depth[x] > depth[y]) x = fa[x][lg[depth[x] - depth[y]] - 1];
  if (x == y) return x;
  for (int k = lg[depth[x]] - 1; k >= 0; k--) {
    if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k];
  }
  return fa[x][0];
}

// 用dfs求最大压力，回溯时将子树的权值加上
void get_ans(int u, int father) {
  for (int i = head[u]; i; i = edge[i].next) {
    int to = edge[i].to;
    if (to == father) continue;
    get_ans(to, u);
    power[u] += power[to];
  }
  ans = max(ans, power[u]);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> k;
  int x, y;
  for (int i = 1; i <= n; i++) {
    lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
  }
  for (int i = 1; i <= n - 1; i++) {  // 建图
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  int s, t;
  for (int i = 1; i <= k; i++) {
    cin >> s >> t;
    int ancestor = lca(s, t);
    // 树上差分
    power[s]++;
    power[t]++;
    power[ancestor]--;
    power[fa[ancestor][0]]--;
  }
  get_ans(1, 0);
  cout << ans << '\n';
  return 0;
}

Bài tập

Tiền tố tổng:

Tiền tố tổng đa chiều:

Tiền tố tổng trên cây:

Hiệu sai phân:

Hiệu sai phân đa chiều:

Hiệu sai phân trên cây:

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply