Let there be some array. In the absence of changes, we can quickly (faster than a line) find the value of some functions on a subsegment of this array. To do this, we need to use additional memory and do a pre-calculation.
For example, we need to quickly find the sum on some segment of the array.
Let's get an array of prefix sums, in which the index i will be the sum of all elements of the array with indices less than or equal to i.
a[] – given array, p[] – array of prefix sums
Array count p:
Obviously p[0] = a[0]. Note that we can easily recalculate p[i] via p[i – 1], because the amount on the i prefix is the amount on the i prefix – 1 + a[i].
Thus, the code for calculating prefix sums looks like this:
int a[n], p[n];
p[0] = a[0< /span>];
for (int i = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Further, we note that the sum on the segment – the difference between the two sums on the prefix.
Green = red – blue
Thus, if it is necessary to find the sum on the interval [l,r], then the answer is p[r] – p[l-1].
However, if l – 1 element may not exist. In order to do without if’s, you can enter 1-indexing, and a[0] and p[0] will have neutral values (0 for the sum).
Note that this technique is a special case of the inclusion-exclusion formula, so in this way it is possible to store not only sums, but also other functions, such as multiplication and xor.