Здравствуйте, я хотел бы рассказать, как можно используя Дерево Фенвика: ↵
↵
↵
1) Изменять на отрезке с l по r O(log (n))↵
↵
↵
2) Узнавать значение в точке O(log (n))↵
↵
↵
(в интернете не нашёл такого)↵
↵
↵
Представим, что у нас уже есть написанное Дерево Фенвика(дальше ДФ) и массив, в котором все элементы равны 0, и мы умеем изменять в точке и находить сумму на префиксе.↵
↵
↵
Теперь, давайте, когда нам придёт запрос изменения с l по r на x, вызовем update(l, x) и update(r + 1, -x)↵
↵
↵
А когда прийдёт запрос на значение в точке i, давайте возьмём сумму на префиксе от 0 до i, утверждается, что эта сумма и будет равна элементу массива, уже изменённого. Попробую объяснить почему так: Рассмотрим нашу точку i, и случайный отрезок из запросов, l, r.↵
↵
↵
1 случай: если мы внутри отрезка(i >= l && i <= r), то мы учтём значение в точке l↵
2 слуай: мы левее отрезка(i < l), то мы не учтём этот отрезок, т.к. l > i↵
↵
↵
3 случай: мы правее отрезка(i > r), то мы учтём значение x в l, и значение -x в r + 1, откуда следует, что они взаимоуничтожатся, и мы можно сказать не смотрим на этот отрезок.↵
Если у вас есть возможность, то советую использовать ДФ вместо ДО, т.к. у ДФ меньше константа и оно требует меньше памяти, да и пишется быстрее.↵
↵
↵
Приведу время работы и объём потребляемой памяти в задаче на изменение отрезка и значение в точке.↵
↵
↵
ДО — 0.874мс, 7.3МБ↵
↵
↵
ДФ — 0.092мс, 1200КБ↵
↵
↵
Если увидели недочёт в посте, то пишите в коментарии, изменю
↵
↵
1) Изменять на отрезке с l по r O(log (n))↵
↵
↵
2) Узнавать значение в точке O(log (n))↵
↵
↵
(в интернете не нашёл такого)↵
↵
↵
Представим, что у нас уже есть написанное Дерево Фенвика(дальше ДФ) и массив, в котором все элементы равны 0, и мы умеем изменять в точке и находить сумму на префиксе.↵
↵
↵
Теперь, давайте, когда нам придёт запрос изменения с l по r на x, вызовем update(l, x) и update(r + 1, -x)↵
↵
↵
А когда прийдёт запрос на значение в точке i, давайте возьмём сумму на префиксе от 0 до i, утверждается, что эта сумма и будет равна элементу массива, уже изменённого. Попробую объяснить почему так: Рассмотрим нашу точку i, и случайный отрезок из запросов, l, r.↵
↵
↵
1 случай: если мы внутри отрезка(i >= l && i <= r), то мы учтём значение в точке l↵
2 слуай: мы левее отрезка(i < l), то мы не учтём этот отрезок, т.к. l > i↵
↵
↵
3 случай: мы правее отрезка(i > r), то мы учтём значение x в l, и значение -x в r + 1, откуда следует, что они взаимоуничтожатся, и мы можно сказать не смотрим на этот отрезок.↵
Если у вас есть возможность, то советую использовать ДФ вместо ДО, т.к. у ДФ меньше константа и оно требует меньше памяти, да и пишется быстрее.↵
↵
↵
Приведу время работы и объём потребляемой памяти в задаче на изменение отрезка и значение в точке.↵
↵
↵
ДО — 0.874мс, 7.3МБ↵
↵
↵
ДФ — 0.092мс, 1200КБ↵
↵
↵
Если увидели недочёт в посте, то пишите в коментарии, изменю
