Префикстик суммалар
Префикстик суммалар: «кесиндидеги сумма» суроосуна O(1) убакытта жооп; айырма массиви.
Кырдаал: n сандан турган массив жана q суроо «l-элементтен r-элементке чейинки сумма канча?». Ар бир суроону цикл менен эсептөө — O(n·q): n = q = 10⁵ болгондо бул 10¹⁰ амал, үмүтсүз.
Чечими — алдын ала эсептөө. Префикстик суммалардын массивин түзөбүз: p[i] = биринчи i элементтин суммасы. Ошондо [l, r] кесиндисиндеги сумма — жөн гана p[r] - p[l-1]: «r ге чейинки суммадан» «l-1ге чейинки сумманы» кемиттик. Ар бир суроо — O(1), баары чогуу — O(n + q).
Киргизиңиз: 5 2, массив 1 2 3 4 5, андан кийин суроолор: 2 4 жана 1 5
Эстеп калууга арзый турган майда-чүйдөлөр:
• бирден башталган индексация жана p[0] = 0 l = 1 өзгөчө учурунан куткарат;
• префикстик суммалар long long түрүндө топтолот — жүз миң миллиарддын суммасы int түрүнө батпайт;
• ушул эле идея 2D форматта иштейт: префикс-таблица тик бурчтуктагы сумманы O(1) убакытта берет.
Күзгүдөй ыкма — айырма массиви: эгер суроолор тескерисинче кесиндилерди ӨЗГӨРТСӨ («l ден r ге чейинкилердин баарына x кошуу»), ал эми жооп аягында бир жолу керек болсо, айырмаларды сактаңыз: d[l] += x, d[r+1] -= x, аягында массивди айырмалардын өзүнүн префикстик суммалары менен калыбына келтириңиз.
Айырма массиви. Киргизиңиз: 5 2, андан кийин суроолор «1 3 2» жана «2 5 1»
Тапшырма: префикстик суммалардын массиви боюнча суммасы нөл болгон кесиндилердин санын табыңыз (кеңеш: [l, r] суммасы нөл, качан p[r] == p[l-1]; бирдей префикстерди map аркылуу эсептеңиз — бул эки теманын айкалышы!).
Сабакты өттүм деп белгилеп, бинардык издөөгө өтүңүз.