Difference array
Në shqip: Vargu i diferencave
ShpjegimiSQ
Për të shtuar një vlerë në shumë intervale njëherësh: shëno +x në fillim dhe −x pas fundit, pastaj llogarit shumat e prefiksit në fund. Shumë përditësime intervalesh bëhen në O(1) secili.
EnglishEN
To add a value over many ranges at once: mark +x at the start and −x after the end, then compute prefix sums at the end. Many range updates become O(1) each.
Si ta mendosh
Si të shënosh në kalendar vetëm fillimin dhe mbarimin e pushimeve, jo çdo ditë.
Lexoje në anglisht
Like marking only the start and end of holidays on a calendar, not every day.
Shembull kodipython
d = [0] * (n + 1)
for a, b, x in perditesimet: d[a] += x; d[b + 1] -= x
vlerat = list(itertools.accumulate(d))[:n]