Prefix sum és különbség gondolkodás

A prefix sum arra tanít, hogyan fizess egyszer egy előfeldolgozási költséget azért, hogy a későbbi range kérdések olcsók legyenek. A difference array ennek a duális ötlete: a range update hatását rögzíted olcsón most, a végső értékeket pedig később materializálod.

1. Definíció

Miről szól ez a téma?

Ez a téma arról szól, hogyan alakítod a sok ismétlődő range munkát inkrementális state-té.

Ahelyett, hogy minden alkalommal újraszámolnád egy részintervallum összegét, előre felépítesz elég szerkezetet ahhoz, hogy a range eredmény gyorsan levezethető legyen.

Ugyanez a gondolkodás az update-ekre is kiterjed.

Ahelyett, hogy egy range update minden elemét módosítanád, csak azt rögzíted, hol kezdődik a hatás és hol szűnik meg.

A két fő ötlet

Ez a fejezet két összekapcsolt mintát fog össze:

• prefix sum gyors range querykhez,
• difference array gyors range update-ekhez.

Miért fontos ez interjún?

Sok range feladat úgy van megfogalmazva, hogy a brute-force megoldás egy belső loopot hív meg újra és újra.

Ez kis példákon működhet, de nagy constrainteknél szétesik.

A prefix gondolkodás átfordítja a modellt a „minden range-et külön kiszámolok” szemléletből a „korábbi felhalmozott munkát újrahasznosítom” szemléletbe.

Mi NEM ez a téma?

Ez még nem segment tree, Fenwick tree vagy lazy propagation.

Ez a korábbi, interjúkban sokkal gyakoribb réteg, ahol ilyen eszközökkel dolgozol:

• running sum,
• prefix tábla,
• prefix értékekre épülő hash map,
• difference marker.

Felismerési jelek

A témának be kell kapcsolnia, ha a prompt ilyen dolgokról beszél:

• range sum query,
• sok ismételt subarray sum,
• valamilyen tulajdonságú subarray-ek számlálása,
• vagy sok range increment alkalmazása.

2. Alapfogalmak

Running sum

A running sum az a total, amelyet balról jobbra haladva fokozatosan felépítesz.

Ez a prefix sum alapja.

Prefix sum

A prefix sum az i indexnél a kezdeti szakasz összegét tárolja egy adott pontig.

Egy gyakori konvenció:

• prefix[0] = 0,
• prefix[i + 1] = prefix[i] + nums[i].

Ez a formula tisztább range képleteket ad.

Range sum prefixből

Ha van prefix tömböd, akkor a [left, right] intervallum összege:

$$ \text{rangeSum}(left, right) = prefix[right + 1] - prefix[left] $$

Ez megszünteti a belső loopot.

Előfeldolgozás versus lekérdezési költség

A prefix sum egy egyszeri előfeldolgozási passzt cserél olcsóbb ismételt querykre.

Sokszor pontosan ezt akarja a feladat.

Prefix state mint modell, nem csak mint tömb

A prefix értékeket nem mindig csak közvetlen range sum queryhez tárolod.

Néha azt követed, egy prefix érték hányszor jelent meg eddig.

Ez a kulcs az ilyen feladatokhoz:

• subarray sum equals k,
• zero-sum subarray count,
• balanced prefix minták.

Difference array

A difference array a szomszédos pozíciók közti változást tárolja.

Ahelyett, hogy egy [left, right] range increment minden elemére ráírnád az update-et, megteheted, hogy:

• hozzáadod a value értéket a left indexnél,
• levonod a value értéket a right + 1 indexnél, ha létezik,
• majd egy running summal visszaépíted a végső tömböt.

Miért működik a difference array?

Mert az increment a bal határtól kezd hatni, és közvetlenül a jobb határ után megszűnik.

Elég ezeket a boundary pontokat rögzíteni.

Inclusive boundaryk számítanak

A range képletek gyakran off-by-one hibák miatt romlanak el.

Mindig egyértelműen meg kell mondanod, hogy a tartomány:

• inclusive,
• exclusive,
• vagy half-open.

A negatív számok számítanak

A sliding window technikák gyakran nemnegatív értékekre támaszkodnak.

A prefix-sum-plus-map megoldások nem igénylik ugyanezt a feltételezést.

Ez nagyon fontos különbség.

Felismerő mondat

Erős ösztön lehet ez:

• „Ha ugyanazokat az átfedő range-eket újraszámolom, prefix sum kellhet.”
• „Ha ugyanazokat az átfedő update-eket újraalkalmazom, difference array kellhet.”

3. Gyakorlati használat

Gyors range sum queryk

Ha sok sum queryt kell megválaszolni egy nem módosuló tömbön, a prefix sum általában az első eszköz, amit érdemes kipróbálni.

Target összegű subarray-ek számlálása

Ha a prompt azt kérdezi, hány olyan subarray van, amelynek összege k, gondolj prefix sumra és egy mapre a korábban látott prefix értékekkel.

A kulcsazonosság:

$$ currentPrefix - earlierPrefix = k $$

Tehát ha a jelenlegi prefix s, akkor azt kell tudnod, hányszor fordult elő korábban az s - k érték.

Sok range increment

Ha a prompt sok ilyen műveletet kér, hogy „adj hozzá value-t minden indexhez left és right között”, akkor a közvetlen per-range loop túl lassú lehet.

Itt lesz értékes a difference gondolkodás.

Intuíció építése

A prefix sum arról szól, hogy megkérdezed:

• mekkora total gyűlt össze eddig,
• és két total különbségéből hogyan kapom meg a kívánt range-et.

A difference array arról szól, hogy megkérdezed:

• hol kezdődik egy hatás,
• hol ér véget,
• és később vissza tudom-e építeni a teljes eredményt.

Interjús magyarázati minta

Egy tiszta magyarázat gyakran így hangzik:

1. „A naiv megoldás átfedő munkát számol újra.”
2. „A queryk vagy update-ek közös szerkezetet osztanak meg.”
3. „Ezt az ismétlődő munkát át tudom tenni egy előfeldolgozási passzba.”
4. „Így minden query vagy minden update sokkal olcsóbb lesz.”

Mikor ne erőltesd vakon?

Ne erőltesd a prefix sumot, ha:

• a művelet nem additív,
• az update és a query is dinamikusan változik bonyolultabban,
• vagy a feladatot más technika kezeli jobban.

De a range-alapú interjúalapoknál ezek rendkívül gyakori minták.

4. Kódpéldák

Alap példa — prefix sum építése range querykhez

public class RangeSumQuery {
    private final int[] prefix;

    public RangeSumQuery(int[] nums) {
        this.prefix = new int[nums.length + 1];
        for (int index = 0; index < nums.length; index++) {
            prefix[index + 1] = prefix[index] + nums[index];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

Miért működik:

• az előfeldolgozás lineáris,
• minden query konstans idejű,
• és a formula tiszta, ha prefix[0] = 0.

Köztes példa — subarray sum equals `k`

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {
    public static int countSubarrays(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);

        int prefix = 0;
        int result = 0;

        for (int value : nums) {
            prefix += value;
            result += seen.getOrDefault(prefix - target, 0);
            seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
        }

        return result;
    }
}

Ez az egyik legfontosabb prefix-sumos interjúminta.

Nem csak a prefix értékeket tárolod.

Azt is tárolod, egy prefix érték hányszor fordult elő.

Köztes példa — difference array range incrementhez

public class RangeIncrement {
    public static int[] applyUpdates(int length, int[][] updates) {
        int[] diff = new int[length];

        for (int[] update : updates) {
            int left = update[0];
            int right = update[1];
            int value = update[2];

            diff[left] += value;
            if (right + 1 < length) {
                diff[right + 1] -= value;
            }
        }

        int[] result = new int[length];
        int running = 0;

        for (int index = 0; index < length; index++) {
            running += diff[index];
            result[index] = running;
        }

        return result;
    }
}

Az update költsége konstans lesz műveletenként, és a végső materializálás egyetlen passz.

Haladó példa — kapacitásellenőrzés sok út után

public class CarPoolingCheck {
    public static boolean canCarryAllTrips(int[][] trips, int capacity) {
        int[] diff = new int[1001];

        for (int[] trip : trips) {
            int passengers = trip[0];
            int from = trip[1];
            int to = trip[2];

            diff[from] += passengers;
            diff[to] -= passengers;
        }

        int currentLoad = 0;
        for (int change : diff) {
            currentLoad += change;
            if (currentLoad > capacity) {
                return false;
            }
        }

        return true;
    }
}

Ez remek példa arra, hogy difference gondolkodással inkább a change pointok számítanak, nem minden egyes index a range-en belül.

Gyakori hiba — off-by-one prefix formula

public class BrokenRangeSum {
    public static int sumRange(int[] prefix, int left, int right) {
        return prefix[right] - prefix[left];
    }
}

Ha a prefix[i] azt jelenti, hogy az i index előtti elemek összege, akkor ez a formula hibás inclusive [left, right] range-re.

A helyes formula ezzel a konvencióval:

return prefix[right + 1] - prefix[left];

5. Trade-offok

Szempont	Részletek
⚡ Performance	A prefix előfeldolgozás lineáris, és az ismételt range queryket konstans idejűvé teheti. A difference array minden range update-et konstans idejűvé tesz a végső visszaépítés előtt.
💾 Memory	Extra memóriát fizetsz a prefix vagy difference struktúráért, hogy megszűnjön az ismételt munka.
🔧 Maintainability	A képletek elegánsak, ha az indexelési konvenció tiszta, de a homályos boundaryk könnyen review-problémává válnak.
🔄 Flexibility	Additív range logikára kiváló, de nem univerzális válasz minden dinamikus query/update problémára.

Performance trade-off: Egyszer fizetsz, hogy sokszor spórolj.

Memory trade-off: Az extra tömbök szinte mindig megérik, ha sok az ismétlődő range munka.

Maintainability trade-off: Az olyan konvenciók, mint a prefix[0] = 0, sokkal biztonságosabbá teszik a kódot.

Flexibility trade-off: A prefix és difference minták erősek, de nem helyettesítenek minden advanced range adatstruktúrát.

6. Gyakori hibák

1. Brute-force range loopok ismételt használata
   Ez tipikusan arra utal, hogy elmaradt a shared work felismerése.

2. Rossz prefix indexelési konvenció
   Sok hiba abból jön, hogy nem konzisztens, mit jelent a prefix[i].

3. A kezdeti 0 -> 1 base case elfelejtése prefix-map feladatnál
   Ez kritikus az index 0-nál kezdődő subarray-ekhez.

4. Sliding window használata negatív számok mellett
   Ilyenkor sokszor prefix-sum plus map megoldás kell inkább.

5. A difference update leállításának elfelejtése a right + 1 helyen
   Enélkül a hatás túl sokáig marad érvényben.

6. Kilépés a tömbhatáron túlra
   A right + 1 használatát boundary checkkel kell védeni.

7. Query logika és update logika összekeverése
   A prefix sum gyors querykre jó; a difference array gyors update-ekre jó.

7. Mélyebb összefüggések

A mélyebb mentális váltás

Itt az igazi erő nem maga a formula.

Hanem az a váltás, hogy a közvetlen munkáról átállsz az újrahasznosítható felhalmozott state-re.

Ha átfedő subarray-eket vagy átfedő update-eket látsz, akkor azt kell kérdezned, hogy a korábbi munka ismételhető-e helyett újrahasznosítható-e.

A prefix sum nem csak összeadásról szól

A beginnerszintű benyomás gyakran az, hogy a prefix sum „csak kumulatív összeadás”.

A valódi trükk azonban két felhalmozott state kivonása egy köztes range izolálására.

Ezért ilyen újrahasznosítható a módszer.

A prefix map tovább viszi az ötletet

Amikor a prefix sumot map-pel párosítod, már nem csak explicit range-ekben gondolkodsz, hanem a korábbi és jelenlegi felhalmozott state közti kapcsolatokban.

Ezért lesz sokkal könnyebb a subarray sum equals k típusú feladat.

A difference array ennek a tükörképe

A prefix sum sok queryt válaszol meg egy felhalmozási passz után.

A difference array sok update-et nyel el előbb, majd egy felhalmozási passzal adja vissza a végső értékeket.

Ezt a szimmetriát érdemes megjegyezni.

Miért érződnek ezek „okosnak” interjún?

Azért, mert az ismételt lokális munkát kompakt globális modellel helyettesítik.

Az interjúztatók ezt szeretik, mert pattern recognitiont mutat, nem csak implementációt.

Java-specifikus megjegyzések

Java-ban a tömbök különösen tisztává teszik ezeket a mintákat.

A fő veszély nem a szintaxis, hanem az indexelési fegyelem.

Ha világosan definiálod, mit jelent a prefix[i], és hogyan értelmezed a range boundarykat, az implementáció egyenes lesz.

8. Interjúkérdések

Q: Miért jó a prefix[0] = 0?
A: Tisztábbá teszi a range képleteket, és természetesen támogatja az index 0-tól induló intervallumokat.

Q: Mi a subarray sum equals k fő ötlete?
A: A jelenlegi prefix sum mellé azt nézed, hányszor fordult elő korábban a currentPrefix - k érték.

Q: Miért fontos a seen.put(0, 1) base case?
A: Mert kezeli azokat a subarray-eket, amelyek index 0-nál indulnak és már önmagukban kiadják a targetet.

Q: Mi a difference array alapötlete?
A: Azt rögzíti, hol kezdődik és hol szűnik meg egy range update hatása, majd running summal visszaépíti a végső értékeket.

Q: Mi a gyakori bugforrás ebben a témában?
A: Az off-by-one indexelés és a nem tisztázott boundary konvenció.

9. Fogalomtár

Fogalom	Definíció
prefix sum	Felhalmozott összeg a kezdetektől egy adott pontig.
running sum	Balról jobbra haladva fokozatosan épített összeg.
range query	Egy összefüggő intervallumra vonatkozó kérdés, például left-től right-ig vett összeg.
difference array	Olyan struktúra, amely range update-ek boundary változásait tárolja.
preprocessing	Előre elvégzett munka, amely a későbbi műveleteket olcsóbbá teszi.
materialization	A végső értékek visszaépítése tömörített state-ből.
off-by-one error	Olyan bug, amelyben egy boundary egy indexszel elcsúszik.

10. Cheatsheet

• Az ismételt range sum gyakran prefix sumot jelez.
• Az ismételt range increment gyakran difference arrayt jelez.
• Tiszta prefix konvenció a prefix[0] = 0.
• Inclusive range sum gyakran prefix[right + 1] - prefix[left].
• subarray sum equals k feladatnál a currentPrefix - k értéket keresd a mapben.
• Prefix map esetén gyakran kell a 0 -> 1 induló állapot.
• Difference update left-nél indul és right + 1-nél áll meg.
• A right + 1 boundaryt mindig védd.
• Negatív számok gyakran megtörik az egyszerű sliding window intuíciót.
• A shared work felismerése az előfeldolgozás legfontosabb jele.