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

Проблем

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

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

function rangeSum(revenue, a, b) {
  let sum = 0;
  for (let day = a; day <= b; day++) {
    sum += revenue[day];
  }
  return sum;
}

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

const revenue = revenueOf(1000);
const queries = queriesOf(1000);
let total = 0;
let additions = 0;
for (const [a, b] of queries) {
  total += rangeSum(revenue, a, b);
  additions += b - a + 1;
}
console.log(`заявки: ${queries.length}`);
console.log(`сбор на отговорите: ${total}`);
console.log(`събирания: ${additions}`);

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

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

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

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

function revenueOf(n) {
  return Array.from({ length: n }, (_, i) => 50 + ((i * 37) % 451));
}

function queriesOf(n) {
  const queries = [];
  for (let k = 0; k < n; k++) {
    const a = (k * 7919) % n;
    queries.push([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).

Виж го

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

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, b) {
  return prefix[b + 1] - prefix[a];
}

const revenue = [120, 80, 150, 90, 200, 60, 110, 140];
const prefix = buildPrefix(revenue);
console.log(`prefix: [${prefix.join(", ")}]`);
console.log(`дни 2–5: ${rangeSum(prefix, 2, 5)}`);

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

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, 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. Така се вижда, че той е сборът на всичко вляво от границата, а един период е разликата между две граници.

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

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

JavaScript няма готови префиксни суми. Цикълът от горе е обичайният начин. С reduce може да се напише на един ред, но не става по-ясно.

Препълване. Числата в JavaScript са точни до 2⁵³, около 9 · 10¹⁵. Оборот в центове стига дотам чак при невероятни суми. В Java и C# масивът се прави long, защото там int свършва при 2 147 483 647.

Пробвай

Предвиди prefix

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

const revenue = [30, 50, 20];
const prefix = buildPrefix(revenue);
console.log(`prefix: [${prefix.join(", ")}]`);

Отговор

prefix: [0, 30, 80, 100]

prefix: [30, 80, 100]

prefix: [0, 30, 50, 20]

Пробвай

Попълни

Оборотът от ден 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 €:

const revenue = [120, 80, 150, 90, 200, 60, 110, 140];
const prefix = buildPrefix(revenue);
console.log(`дни 2–5: ${rangeSum(prefix, 2, 5)}`);

дни 2–5: 350

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

Виж го

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

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

const revenue = revenueOf(1000);
const queries = queriesOf(1000);
const prefix = buildPrefix(revenue);
let operations = revenue.length;
let total = 0;
for (const [a, b] of queries) {
  total += rangeSum(prefix, a, b);
  operations++;
}
console.log(`заявки: ${queries.length}`);
console.log(`сбор на отговорите: ${total}`);
console.log(`събирания и изваждания: ${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 не пускаме, за да не замръзне страницата.

function buildPrefix(revenue) {
  const prefix = new Array(revenue.length + 1).fill(0);
  for (let i = 0; i < revenue.length; i++) {
    prefix[i + 1] = prefix[i] + revenue[i];
  }
  return prefix;
}

function rangeSum(prefix, a, 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). Всяко място е клетката плюс горния и левия правоъгълник. Ъгълът между тях е броен два пъти, затова се маха веднъж:

function buildPrefix2D(orders) {
  const rows = orders.length;
  const cols = orders[0].length;
  const p = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
  for (let r = 0; r < rows; r++) {
    for (let 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;
}

function rect(p, r1, c1, r2, c2) {
  return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
}

const 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],
];
const p = buildPrefix2D(orders);
console.log(`поръчки вт–ср от 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? Отговорът се пази в речник префикс → колко пъти е виждан:

function countPeriods(profit, target) {
  const seen = new Map([[0, 1]]);
  let prefix = 0;
  let count = 0;
  for (const p of profit) {
    prefix += p;
    count += seen.get(prefix - target) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

const profit = [40, -10, 30, 20, -30, 50, -20, 30, 0, 20];
console.log(`периоди с печалба 50 €: ${countPeriods(profit, 50)}`);

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

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

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

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

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

Пробвай

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

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

const profit = [20, 30, -30, 30];
console.log(`периоди с печалба 50 €: ${countPeriods(profit, 50)}`);

Отговор

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

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

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

Упражнение

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

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

Доставено, продадено, наличност. Складът започва с 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 отпреди първия ден

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

Бисквитки