Как поддерживать операции «прибавить x на отрезке [l, r]» и «получить сумму на отрезке [l, r]» за O(log n)?
Короткий ответ: сегментное дерево с ленивой пропагацией или пара деревьев Фенвика: range add/ range sum через две Fenwick (хранить A и i·A; префикс считается как i·sum(A) − sum(i·A)).
🐸Библиотека собеса по DevOps
Post #1011
802
- 🌚 5