Hãy để có một số mảng. Trong trường hợp không có thay đổi, chúng ta có thể nhanh chóng (nhanh hơn một dòng) tìm giá trị của một số hàm trên một phân đoạn con của mảng này. Để làm điều này, chúng tôi cần sử dụng bộ nhớ bổ sung và thực hiện phép tính trước.
Ví dụ, chúng ta cần tìm nhanh tổng trên một đoạn nào đó của mảng.
Hãy lấy một mảng các tổng tiền tố, trong đó chỉ số i sẽ là tổng của tất cả các phần tử của mảng có chỉ số nhỏ hơn hoặc bằng i.
a[] – mảng đã cho, p[] – mảng tiền tố tổng
Số lượng mảng p:
Rõ ràng p[0] = a[0]. Lưu ý rằng chúng ta có thể dễ dàng tính toán lại p[i] thông qua p[i – 1], bởi vì số tiền trên tiền tố i là số tiền trên tiền tố i – 1 + a[i].
Do đó, mã để tính tổng tiền tố trông như thế này:
int a[n], p[n];
p[0] = a[0< /span>];
cho (int tôi = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Hơn nữa, chúng tôi lưu ý rằng tổng trên phân khúc – sự khác biệt giữa hai khoản tiền trên tiền tố.
Xanh lục = đỏ – màu xanh da trời
Vì vậy, nếu cần tìm tổng trên khoảng [l,r], thì câu trả lời là p[r] – p[l-1].
Tuy nhiên, nếu l – 1 yếu tố có thể không tồn tại. Để thực hiện mà không cần if’s, bạn có thể nhập 1 chỉ mục và a[0] và p[0] sẽ có giá trị trung tính (0 cho tổng).
Lưu ý rằng kỹ thuật này là trường hợp đặc biệt của công thức bao gồm-loại trừ, do đó, theo cách này, không chỉ có thể lưu trữ các tổng mà còn các hàm khác, chẳng hạn như phép nhân và xor.