Префиксен масив
Prefix Array
В тази тема ще покажем как бързо можем да намираме сумата в произволен под-интервал на масив чрез структурата данни "префиксен масив". Ще демонстрираме как може да се справяме с двумерни масиви и да правим константна заявка за цял под-регион.
Автор: Александър Георгиев
Понякога ще ни трябват по-сложни структури данни, които не просто пазят информацията в удобен за достъп начин, ами имат методи, които бързо намират специфична информация. С най-лесната от тях ще се запознаем сега, като нататък ще разгледаме редица по-сложни и по-мощни такива.
Какво е куери?
Преди да ви запознаем с проблема, който искаме да решим, ще ви научим на един термин, който ще срещате
много често оттук нататък. Това е думата
куери (от английски
query) или преведено на Български -
заявка. Куерита може да имате за най-различни неща - от това колко различни елемента вече сме срещнали (с каквито задачи се справихме в предишните теми), през по-сложни от типа на колко е сумата на числата в даден интервал от масив, какъв е минимумът или максимумът, до много сложни питания, за които е нужна редица информация и съответно много сложна структура данни.
Сума в интервал
Даден ви е масив с 1 ≤ N ≤ 100,000 числа с плаваща запетая. Ели се интересува от сумата на числата между индекси idx1 и idx2. Тя ще ви зададе 1 ≤ Q ≤ 100,000 въпроса от тип "Каква е сумата на числата в масива с индекси от idx1 до idx2, включително?". От вас се иска бързо да отговаряте на такива въпроси, за различни валидни индекси.
Този проблем често възниква като подзадача в по-сложни постановки. За него има ефективни решения както ако числата са статични (не се променят, както е в горепосочения случай), така и ако те може да се променят. За сега ще разгледаме много ефективно решение, което се справя с проблема, когато числата не се променят, а в темата за
индексни дървета ще видим как да се справим и ако променяме числата.
Наивно решение
Очевидно наивно решение е за всеки въпрос просто да обхождаме всички числа и да ги сумираме. Това, обаче, е доста неефективно. Представете си, че всички въпроси са за интервала от 0 (или индекс, блзък до 0) до
N-1 (или индекс, близък до
N-1). Каква би била сложността на това решение? Тъй като имаме
Q такива куерита, и всяко от тях е с относително
O(N) сложност, то цялата сложност на нашето решение би била
O(N∙Q). За дадените ограничения това би отнело приблизително 100,000 * 100,000 == 10,000,000,000, или би отнело приблизително 10 секунди на мощен компютър. Това е твърде бавно.
Префиксен масив
Нещото, което не използвахме при тривиалния подход, е, че числата в масива са дадени предварително и не се променят. Помага ли ни това?
Да! Представете си, че имаме масив, в който имаме
сумите на числата от началото на масива, до съответния индекс. Примерно ако имаме начален масив
(3, 13, 5, 5, 9, 7, 42, 1), то този със сумите би бил
(3, 16, 21, 26, 35, 42, 84, 85). С малко мислене можем да видим, че ако ни зададат въпрос за
[idx1, idx2], то реално отговорът е
sums[idx2] - sums[idx1 - 1], където
sums[] е масивът със сумите. Разбира се, трябва да се справим с частния случай ако
idx1 == 0, но освен него това би работело!
Добре, остана да създадем масива
sums[], и сме готови. Как да направим това ефективно? Очевидно, тъй като трябва да запълним
O(N) клетки, то сложността ни ще е поне
O(N). Също така, понеже ни задават
Q куерита, ще имаме поне
O(Q) от това. Макар и тези сложности да не можем да ги избегнем, ще се постараем нашата крайна сложност да е
точно толкова, а не
поне толкова - тоест да постигнем
O(N + Q). Следния код прави именно това:
double
sums[MAX];
// Така питаме за сумата на елементите в интервала [idx1, idx2].
double
query(int
idx1,
int
idx2) {
return
sums[idx2] -
(idx1 >
0
?
sums[idx1 -
1
] :
0.0
);
}
// Тази стъпка изпълняваме само веднъж - преди да започнем с питанията.
void
init(double
a[MAX],
int
n) {
sums[0
] =
a[0
];
for
(int
i =
1
;
i <
n;
i+
+
) {
sums[i] =
sums[i -
1
] +
a[i];
}
}Двумерен префиксен масив
Можем да разширим горната идея и за двумерен масив. В клетката
(row, col) от масива ще пазим сумата на всички елементи, които се намират в правоъгълника
(0, 0) -> (row, col). За да имплементираме куери за под-правоъгълник
(row1, col1) -> (row2, col2), където
row1 ≤
row2 и
col1 ≤
col2, ще ползваме принципа на включване и изключване в неговия най-прост вариант:
- прибавяме региона
(0, 0) -> (row2, col2); - изваждаме региона
(0, 0) -> (row2, col1 - 1); - изваждаме региона
(0, 0) -> (row1 - 1, col2); - прибавяме региона
(0, 0) -> (row1 - 1, col1 - 1).
Нека имаме някакъв масив с 6 реда и 10 колони (за момента не ни интересуват какви числа има в клетките му, само колко пъти ги взимаме по време на куери). Нека правим куери за
(2, 3) -> (4, 7). В таблицата по-долу сме показали по колко пъти сме взели всяка клетка, след горните четири операции:
| +1-1-1+1=0 | +1-1-1+1=0 | +1-1-1+1=0 | +1-1=0 | +1-1=0 | +1-1=0 | +1-1=0 | +1-1=0 | 0 | 0 |
| +1-1-1+1=0 | +1-1-1+1=0 | +1-1-1+1=0 | +1-1=0 | +1-1=0 | +1-1=0 | +1-1=0 | +1-1=0 | 0 | 0 |
| +1-1=0 | +1-1=0 | +1-1=0 | +1=1 | +1=1 | +1=1 | +1=1 | +1=1 | 0 | 0 |
| +1-1=0 | +1-1=0 | +1-1=0 | +1=1 | +1=1 | +1=1 | +1=1 | +1=1 | 0 | 0 |
| +1-1=0 | +1-1=0 | +1-1=0 | +1=1 | +1=1 | +1=1 | +1=1 | +1=1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Можете да видите, че след четирите операции само клетките в региона, който ни интересуваше (
(2, 3) -> (4, 7)), са взети по веднъж - всички останали са прибавени в сумата по нула пъти.
Примерна имплементация на горното нещо:
double
query(int
row1,
int
col1,
int
row2,
int
col2) {
double
ans =
sums[row2][col2];
if
(row1 >
0
) ans -
=
sums[row1 -
1
][col2];
if
(col1 >
0
) ans -
=
sums[row2][col1 -
1
];
if
(row1 >
0
&
&
col1 >
0
) ans +
=
sums[row1 -
1
][col1 -
1
];
return
ans;
}
void
init(double
a[MAX][MAX],
int
n,
int
m) {
for
(int
row =
0
;
row <
n;
row+
+
) {
double
rowSum =
0
;
for
(int
col =
0
;
col <
m;
col+
+
) {
rowSum +
=
a[row][col];
sums[row][col] =
rowSum +
(row >
0
?
sums[row -
1
][col] :
0
);
}
}
}Задачи за тренировка
Подготвили сме ви три задачки за тренировка. Задачата
Cinema от първи кръг на Националната Олимпиада (2011-та година) изисква от вас да приложите същата техника, но в двумерен вариант. Задачата
ShoeShopping изисква да съчетаете префиксния масив с друг стандартен алгоритъм, който вече разгледахме. Задачата
Multi пък изисква малко креативност, но иначе нищо друго, освен префикесн масив. В задачата
Sum of Primes също може да бъде приложен префиксен масив след като бъдат намерени простите числа с
решето на Ератостен.
Страницата е посетена 6779 пъти.