Префиксни суми в C#

Проблем

Таблото, което сумира всеки път

Таблото на магазина показва оборота за избран период: „от ден 120 до ден 340“, „последните 30 дни“, „тази седмица срещу миналата“. Управителите го отварят по много пъти на ден, а всяка графика пита за десетки периоди. Кодът сумира дните на всеки период наново:

static long RangeSum(int[] revenue, int a, int b)
{
    long sum = 0;
    for (int day = a; day <= b; day++)
    {
        sum += revenue[day];
    }
    return sum;
}

Хиляда дни оборот и хиляда заявки:

int[] revenue = RevenueOf(1000);
var queries = QueriesOf(1000);
long total = 0;
long additions = 0;
foreach (var (a, b) in queries)
{
    total += RangeSum(revenue, a, b);
    additions += b - a + 1;
}
Console.WriteLine($"заявки: {queries.Length}");
Console.WriteLine($"сбор на отговорите: {total}");
Console.WriteLine($"събирания: {additions}");

заявки: 1000
сбор на отговорите: 68412493
събирания: 248794

248 794 събирания за хиляда отговора. Дните между две заявки не се сменят, а кодът ги събира пак и пак. Колкото по-дълги са периодите и колкото повече са заявките, толкова по-бавно става таблото.

Откъде са дните и заявките

Оборотът и заявките са по формула, за да ги построят еднакво програмите на четирите езика и сравнението в браузъра по-долу:

static int[] RevenueOf(int n)
{
    var revenue = new int[n];
    for (int i = 0; i < n; i++)
    {
        revenue[i] = 50 + (i * 37) % 451;
    }
    return revenue;
}

static (int A, int B)[] QueriesOf(int n)
{
    var queries = new (int A, int B)[n];
    for (int k = 0; k < n; k++)
    {
        int a = (k * 7919) % n;
        queries[k] = (a, a + (k * 4231) % (n - a));
    }
    return queries;
}

Идеята

Сборът на всичко вляво

Сметни веднъж, за всеки ден, оборота от началото до този ден. Това е префиксна сума (prefix sum): prefix[k] е сборът на първите k дни.

prefix[0] = 0: сборът на нито един ден;
prefix[k + 1] = prefix[k] + revenue[k]: всяко място е предишното плюс един ден.

Масивът е с едно място повече от дните. После всеки период е разлика на две числа. Оборотът от ден a до ден b е дните от 0 до b минус дните от 0 до a − 1:

prefix[b + 1] − prefix[a]

Строенето е n събирания, веднъж. Всяка заявка след това е две четения и едно изваждане, независимо дали периодът е два дни или две години: O(1) на заявка вместо O(n).

Виж го

Префиксите ден по ден

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

int[] revenue = { 120, 80, 150, 90, 200, 60, 110, 140 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"prefix: [{string.Join(", ", prefix)}]");
Console.WriteLine($"дни 2–5: {RangeSum(prefix, 2, 5)}");

prefix: [0, 120, 200, 350, 440, 640, 700, 810, 950]
дни 2–5: 500

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

Стъпка по стъпка, с думи

8 дни оборот. prefix има 9 места: prefix[0] = 0 е сборът на нито един ден.
prefix[1] = prefix[0] + revenue[0] = 0 + 120 = 120: дни 0–0.
prefix[2] = prefix[1] + revenue[1] = 120 + 80 = 200: дни 0–1.
prefix[3] = prefix[2] + revenue[2] = 200 + 150 = 350: дни 0–2.
prefix[4] = prefix[3] + revenue[3] = 350 + 90 = 440: дни 0–3.
prefix[5] = prefix[4] + revenue[4] = 440 + 200 = 640: дни 0–4.
prefix[6] = prefix[5] + revenue[5] = 640 + 60 = 700: дни 0–5.
prefix[7] = prefix[6] + revenue[6] = 700 + 110 = 810: дни 0–6.
prefix[8] = prefix[7] + revenue[7] = 810 + 140 = 950: дни 0–7.
8 събирания, веднъж. Сега заявката: оборотът от ден 2 до ден 5. prefix[6] = 700 € е дни 0–5.
prefix[2] = 200 € е дни 0–1, частта преди периода. Махаме я.
700 − 200 = 500 €: дни 2–5 с две четения и едно изваждане, колкото и дълъг да е периодът.
Строенето струва n събирания веднъж, а всяка заявка след това струва едно изваждане.

В сцената prefix[k] стои на границата между ден k − 1 и ден k. Така се вижда, че той е сборът на всичко вляво от границата, а един период е разликата между две граници.

По-точно, за любопитните

Готовото в езиците.

C# няма готови префиксни суми, нито в масивите, нито в LINQ. Цикълът от горе е обичайният начин.

Препълване. prefix е long, а не int. Последният префикс е оборотът за целия период. В евроцентове за няколко години той минава 2 147 483 647, а int тогава тихо става отрицателно число.

Пробвай

Предвиди prefix

Три дни оборот: 30, 50 и 20 €.

int[] revenue = { 30, 50, 20 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"prefix: [{string.Join(", ", prefix)}]");

Отговор

prefix: [0, 30, 50, 20]

prefix: [0, 30, 80, 100]

prefix: [30, 80, 100]

Пробвай

Попълни

Оборотът от ден a до ден b включително:

return prefix[] - prefix[a];

Идеята

Нулата отпред

Защо масивът е с едно място повече? Може и без: prefix[k] да е сборът на дни 0 до k, включително. Тогава периодът от a до b е prefix[b] − prefix[a − 1]. Но при a = 0 няма място a − 1, и всяка заявка иска проверка „ако a е 0“.

Нулата отпред маха тази проверка. Цената е едно място в масива, а капанът е, че индексите се изместват с едно: prefix[k] е сборът на дни преди k, не до k. Затова тук грешката с единица (off-by-one) е най-честата, както при двоичното търсене.

Пробвай

Намери грешката

Някой е написал префиксите без нулата отпред. Заявката за дни 2–5 трябва да даде 500 €:

int[] revenue = { 120, 80, 150, 90, 200, 60, 110, 140 };
long[] prefix = BuildPrefix(revenue);
Console.WriteLine($"дни 2–5: {RangeSum(prefix, 2, 5)}");

дни 2–5: 350

Избери реда с грешката.

Виж го

Измери: сумиране наново срещу префиксите

Същите хиляда заявки, с префиксите:

int[] revenue = RevenueOf(1000);
var queries = QueriesOf(1000);
long[] prefix = BuildPrefix(revenue);
long operations = revenue.Length;
long total = 0;
foreach (var (a, b) in queries)
{
    total += RangeSum(prefix, a, b);
    operations++;
}
Console.WriteLine($"заявки: {queries.Length}");
Console.WriteLine($"сбор на отговорите: {total}");
Console.WriteLine($"събирания и изваждания: {operations}");

заявки: 1000
сбор на отговорите: 68412493
събирания и изваждания: 2000

Сборът на отговорите е същият, а работата е 2000 операции вместо 248 794: хиляда събирания за prefix и по едно изваждане на заявка. Пусни двата начина в браузъра. n е и броят дни, и броят заявки:

Сумиране наново за всяка заявка O(n²)
Префиксни суми O(n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Сумиране наново за всяка заявка	10	248 794	≈ 2 487 940 000
Префиксни суми	20	2000	200 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

static long[] BuildPrefix(int[] revenue)
{
    var prefix = new long[revenue.Length + 1];
    for (int i = 0; i < revenue.Length; i++)
    {
        prefix[i + 1] = prefix[i] + revenue[i];
    }
    return prefix;
}

static long RangeSum(long[] prefix, int a, int b)
{
    return prefix[b + 1] - prefix[a];
}

Сумирането наново е O(n) на заявка, O(n²) за n заявки. С префиксите е O(n) веднъж и O(1) на заявка. Цената е памет: един масив с n + 1 числа.

Двумерни префиксни суми: поръчките по ден и час

Топлинната карта на поръчките е таблица: редовете са дни от седмицата, колоните са часове. Въпросът е „колко поръчки има във вторник и сряда от 10 до 13 ч“, тоест сборът в правоъгълник.

p[r][c] е сборът на правоъгълника от горния ляв ъгъл до ред r − 1 и колона c − 1, пак с нули отпред (ред 0 и колона 0). Всяко място е клетката плюс горния и левия правоъгълник. Ъгълът между тях е броен два пъти, затова се маха веднъж:

static int[,] BuildPrefix2D(int[,] orders)
{
    int rows = orders.GetLength(0);
    int cols = orders.GetLength(1);
    var p = new int[rows + 1, cols + 1];
    for (int r = 0; r < rows; r++)
    {
        for (int c = 0; c < cols; c++)
        {
            p[r + 1, c + 1] = orders[r, c] + p[r, c + 1] + p[r + 1, c] - p[r, c];
        }
    }
    return p;
}

static int Rect(int[,] p, int r1, int c1, int r2, int c2)
{
    return p[r2 + 1, c2 + 1] - p[r1, c2 + 1] - p[r2 + 1, c1] + p[r1, c1];
}

int[,] orders = {
    { 3, 8, 12, 9, 5, 4 },
    { 2, 7, 14, 11, 6, 3 },
    { 4, 9, 15, 10, 7, 5 },
    { 1, 6, 11, 8, 4, 2 },
};
var p = BuildPrefix2D(orders);
Console.WriteLine($"поръчки вт–ср от 10 до 13 ч: {Rect(p, 1, 1, 2, 3)}");

поръчки вт–ср от 10 до 13 ч: 66

Заявката е същата идея: целият правоъгълник до долния десен ъгъл, минус лентата отгоре, минус лентата отляво, плюс ъгъла, който е махнат два пъти. Четири четения за правоъгълник от каквато и да е големина.

Идеята

Колко периода дават точно 50 €

Магазинът има дни на загуба: върнатите поръчки се вадят от оборота. Въпросът е колко периода от поредни дни имат печалба точно 50 €.

Всеки период от ден i до ден j е разлика на два префикса: prefix[j + 1] − prefix[i]. Тя е 50 точно когато prefix[i] = prefix[j + 1] − 50. Значи вървиш по дните, пазиш текущия префикс и питаш: колко пъти досега съм виждал префикс, равен на текущия минус 50? Отговорът се пази в речник префикс → колко пъти е виждан:

static int CountPeriods(int[] profit, int target)
{
    var seen = new Dictionary<int, int> { [0] = 1 };
    int prefix = 0;
    int count = 0;
    foreach (int p in profit)
    {
        prefix += p;
        count += seen.GetValueOrDefault(prefix - target);
        seen[prefix] = seen.GetValueOrDefault(prefix) + 1;
    }
    return count;
}

int[] profit = { 40, -10, 30, 20, -30, 50, -20, 30, 0, 20 };
Console.WriteLine($"периоди с печалба 50 €: {CountPeriods(profit, 50)}");

периоди с печалба 50 €: 8

Едно минаване по дните и по едно търсене в hash таблица на ден: O(n). С два вложени цикъла по всички периоди би било O(n²). Речникът тук е брояч: колко пъти е видяна всяка стойност. Това е отделна техника, на нея е следващият урок.

По-точно, за любопитните

seen започва с 0 → 1, защото префиксът преди първия ден е 0. Без него периодите, които започват от ден 0, не се броят.

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

Пробвай

Предвиди броя

Четири дни печалба: 20, 30, −30 и 30 €. Колко периода от поредни дни дават точно 50 €?

int[] profit = { 20, 30, -30, 30 };
Console.WriteLine($"периоди с печалба 50 €: {CountPeriods(profit, 50)}");

Отговор

периоди с печалба 50 €: 3

периоди с печалба 50 €: 2

периоди с печалба 50 €: 1

Упражнение

Складът по дни

Реши задачата в редактора си.

Доставено, продадено, наличност. Складът започва с 40 бройки от един продукт. За десет дни имаш два масива:

доставени: 0, 25, 0, 30, 10, 0, 40, 0, 15, 0;
продадени: 12, 8, 15, 9, 20, 11, 7, 18, 10, 14.

Построй префиксите на двата масива. За периодите дни 2–5, 0–9 и 6–8 отпечатай колко е доставено, колко е продадено и каква е наличността в края на последния ден. Всеки отговор трябва да е с няколко четения от префиксите, без цикъл по дните.

дни 2–5: доставени 40, продадени 55, наличност в края 30
дни 0–9: доставени 120, продадени 124, наличност в края 36
дни 6–8: доставени 55, продадени 35, наличност в края 50

Още задачи

Средна поръчка за период. Освен оборота имаш и броя поръчки по дни. Средната стойност на поръчка не се събира, но двете суми се събират. Как ще отговаряш на „средна поръчка от ден a до ден b“?
Най-добрата седмица. С префиксите намери седемте поредни дни с най-голям оборот. Колко операции прави това за 365 дни?
Топлинната карта. Добави към двумерните суми петък и събота и намери двучасовия прозорец с най-много поръчки за цялата седмица.

Тест

Провери се

1. Оборотът за четири дни е 10, 20, 30 и 40 €. Кой е prefix?[0, 10, 20, 30, 40][10, 30, 60, 100][0, 10, 30, 60, 100]

2. Кое дава оборота от ден a до ден b включително?prefix[b] − prefix[a]prefix[b + 1] − prefix[a + 1]prefix[b + 1] − prefix[a]

3. Вчерашният оборот се поправя заради върната поръчка. Какво става с prefix?Сменя се само едно мястоНищо: prefix не зависи от вчераСменят се всички места след този ден: поправката струва O(n)

4. В countPeriods речникът seen започва с 0 → 1. Защо?Без значение е, само ускоряваЗа да не е празенЗаради периодите, които започват от ден 0: за тях се търси префикс 0 отпреди първия ден

Префиксни суми

Бисквитки