Есть два вида запросов:
Как быстро отвечать на них? Если всего q тестов, то я знаю тупое решение за O(q*n*log(n)) - строить дерево отрезков, для запросов первого типа добавлять x отрезку, а для второго типа для каждого элемента от l до r подниматься по дереву и считать сумму.
можно на каждом узле хранить сумму левой ветки и правой ветки. С этим на первый вопрос можно будет ответить за O(\log n). На второй как минимум можно O((l-r)\log n), надо подумать можно ли лучше
А вообще, если есть динамичный массив, то кажется можно его использовать вместе с кумулятивным массивом. Тогда первый ответ O(1), второй O(n).
Для q тестов и l=1, r=n и выходит qnlog
Ну а че насчет массива? для q запросов O(qn)
Это стандартная задача которую можно решать несколькими способами.
Судя по вопросу вы уже знаете дерево отрезков. Ну и с помощью этой универсальной структуры данных мы можем решить задачу за O(\log (n)) на первый запрос и за O(\log (n)) на второй запрос, суммарно O(q * \log (n)).
Давайте разберёмся с вторым запросом. Заметим что не обязательно обновлять все вершины в которые входят элементы из отрезка который мы обновляем.
Пусть второй запрос это l \space r \space x.
t_v - сумма на отрезке за который отвечает вершина v
l_v - левая граница отрезка за который отвечает вершина v
r_v - правая граница отрезка за который отвечает вершина v
(я обычно пишу ДО на отрезках, а не на полуинтервалах)
Пусть есть вершина v для которой выполняется l \leq l_v \leq r_v \leq r, выполняется ли для её предка p такое что l \leq l_p \leq r_p \leq r, если это правда то не нужно посещать эту вершину во время обновления(дальше скажу почему). Если это не правда то давайте запомним в вершине то что мы должны к каждой вершине u в поддереве элемента v добавить значение (r_u - l_u + 1) * x, и потом когда нам понадобится использовать значения в вершине v мы просто изменим значение t_v в вершине v и протолкнём это обновление в детей вершины v. Как нам это хранить? Давайте в каждой вершине хранить значение z_v которое хранит сумму всех x которые мы должны будем протолкнуть.
Давайте посмотрим как будет выглядеть проталкивание:
t_v = t_v + (r_v - l_v + 1) * z_v
if (r_v \neq l_v) {
\space \space \space \space z_{v*2} += z_v
\space \space \space \space z_{v*2+1} += z_v
}
z_v = 0.
Просто обновляем сумму на отрезке за который отвечает вершина v, потом проталкиваем обновление в детей(не забываем проверить существуют ли у этой вершины дети), и в конце обнуляем z_v так как мы уже прибавили его.
Теперь просто при любом использовании v применяем проталкивание, для удобства можно сделать отдельную функцию push(v).
В обновлении теперь когда отрезок вершины v находится полностью в отрезке запроса мы проделываем такую вещь, z_v += x, push(v) и возвращаемся. Мы протолкнули обновление из v для того чтобы правильно посчитать сумму для её предка. (Не забываем при заходе в вершину v делать push_v). В итоге это будет работать за O(logn).
Теперь вопрос как искать сумму? На самом деле также как в обычном дереве отрезков, просто при заходе в вершину не забываем сделать push(v). А так как мы посетили всех предков вершины v последовательно от корня и от каждого сделали push(v) это значит сумма t_v посчитана правильно. Асимптотика та же O(\log (n)).
Более нормальное объяснение можно найти тут Segment Tree - Algorithms for Competitive Programming или найти статьи в интернете, эта техника называется Segment tree lazy propagation.
Ну и эта же техника применима и для других структур данных в виде деревьев, например это можно использовать в декартовом дереве(ПИВО, Дерамида и другие крутые названия), splay дереве,…