Префиксен масив

Prefix Array

В тази тема ще покажем как бързо можем да намираме сумата в произволен под-интервал на масив чрез структурата данни "префиксен масив". Ще демонстрираме как може да се справяме с двумерни масиви и да правим константна заявка за цял под-регион.

Автор: Александър Георгиев

Понякога ще ни трябват по-сложни структури данни, които не просто пазят информацията в удобен за достъп начин, ами имат методи, които бързо намират специфична информация. С най-лесната от тях ще се запознаем сега, като нататък ще разгледаме редица по-сложни и по-мощни такива.

Какво е куери?

Преди да ви запознаем с проблема, който искаме да решим, ще ви научим на един термин, който ще срещате много често оттук нататък. Това е думата куери (от английски query) или преведено на Български - заявка. Куерита може да имате за най-различни неща - от това колко различни елемента вече сме срещнали (с каквито задачи се справихме в предишните теми), през по-сложни от типа на колко е сумата на числата в даден интервал от масив, какъв е минимумът или максимумът, до много сложни питания, за които е нужна редица информация и съответно много сложна структура данни.

Сума в интервал

Даден ви е масив с 1 ≤ N ≤ 100,000 числа с плаваща запетая. Ели се интересува от сумата на числата между индекси idx₁ и idx₂. Тя ще ви зададе 1 ≤ Q ≤ 100,000 въпроса от тип "Каква е сумата на числата в масива с индекси от idx₁ до idx₂, включително?". От вас се иска бързо да отговаряте на такива въпроси, за различни валидни индекси.

Този проблем често възниква като подзадача в по-сложни постановки. За него има ефективни решения както ако числата са статични (не се променят, както е в горепосочения случай), така и ако те може да се променят. За сега ще разгледаме много ефективно решение, което се справя с проблема, когато числата не се променят, а в темата за индексни дървета ще видим как да се справим и ако променяме числата.

Наивно решение

Очевидно наивно решение е за всеки въпрос просто да обхождаме всички числа и да ги сумираме. Това, обаче, е доста неефективно. Представете си, че всички въпроси са за интервала от 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
+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
+1-1=0	+1-1=0	+1-1=0	+1=1	+1=1	+1=1	+1=1	+1=1
+1-1=0	+1-1=0	+1-1=0	+1=1	+1=1	+1=1	+1=1	+1=1
+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

Можете да видите, че след четирите операции само клетките в региона, който ни интересуваше ((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 също може да бъде приложен префиксен масив след като бъдат намерени простите числа с решето на Ератостен.

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 7523 пъти.

Префиксен масив

Prefix Array

Какво е куери?

Сума в интервал

Наивно решение

Префиксен масив

Двумерен префиксен масив

Задачи за тренировка

Предложете корекция