Двумерное дерево отрезков с массовыми операциями

Revision ru4, by Renedyn, 2021-09-13 19:10:20

Решим следующую задачу:

Дана таблица $$$n \cdot m$$$, поступают 2 вида запросов в онлайне:

1) Прибавить $$$X$$$ на прямоугольнике $$$[l1, r1], [l2, r2]$$$, помимо ассоциативности операция должна быть коммутативна, например присваивание не подойдёт.

2) Посчитать сумму (минимум, ...) на прямоугольнике $$$[l1, r1], [l2, r2]$$$.

Сначала разберём, как делать прибавление на отрезке и сумму на отрезке без пушей в одномерном ДО.

В каждой вершине будем хранить 2 числа: сумму в поддереве и сколько мы прибавим каждому элементу в поддереве, тогда запросом обновления корректно пересчитаем все вершины, которые были посещены нашей функцией

(/predownloaded/8f/d6/8fd6222dd559c4f21e20da5a2dce69f699641a25.png)

Сделаем ДО по первой координате, в каждой вершине которого будет ДО на сумму, отвечающее за прямоугольник [l, r] [0, m]

Tags структуры данных, дерево отрезков

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru26 Russian Renedyn 2021-09-28 10:55:50 165
ru25 Russian Renedyn 2021-09-19 13:43:08 52 Мелкая правка: 'aGhizX\n\n\n' -> 'aGhizX\n\nЗадачи: https://mirror.codeforces.com/contest/341/problem/D\n'
ru24 Russian Renedyn 2021-09-18 22:41:16 1 Мелкая правка: 'не получиться. Но пом' -> 'не получится. Но пом'
ru23 Russian Renedyn 2021-09-16 23:35:10 0 (опубликовано)
ru22 Russian Renedyn 2021-09-16 23:34:42 6 Мелкая правка: 'ет $O(8^k * n)$ и оди' -> 'ет $O(8^k \cdot n)$ и оди' (сохранено в черновиках)
ru21 Russian Renedyn 2021-09-16 21:14:15 1 (опубликовано)
ru20 Russian Renedyn 2021-09-16 21:13:45 38
ru19 Russian Renedyn 2021-09-16 21:10:55 150 Мелкая правка: 'ять будет линейная. \n\nНаск' -> 'ять будет $O(n \cdot log n)$. \n\nНаск'
ru18 Russian Renedyn 2021-09-16 17:26:20 258 Мелкая правка: '87-ru.pdf]А3 недавно п' -> '87-ru.pdf](А3) недавно п'
ru17 Russian Renedyn 2021-09-16 14:31:49 535
ru16 Russian Renedyn 2021-09-16 10:54:11 121 Мелкая правка: '(8^k * n)$. \n\n' -> '(8^k * n)$ и один запрос $O(log^k n)$. \n\n'
ru15 Russian Renedyn 2021-09-15 11:55:10 201
ru14 Russian Renedyn 2021-09-15 11:22:03 2592 Мелкая правка: ' отрезке $[l2, r2]$ $x \cdot (m' -> ' отрезке $sum[v][l2...r2] += x \cdot (m'
ru13 Russian Renedyn 2021-09-14 13:10:49 4 Мелкая правка: 'Paint_\n\n' -> 'Paint_\n\n\n\n'
ru12 Russian Renedyn 2021-09-14 12:57:01 292 Мелкая правка: 'mas[j][i]$\n\n' -> 'mas[j][i]$ \cos (2\theta) = \cos^2 \theta - \sin^2 \theta\n\n'
ru11 Russian Renedyn 2021-09-14 11:18:20 42
ru10 Russian Renedyn 2021-09-14 10:54:15 781 Мелкая правка: 'это учесть в тех вер' -> 'это учесть, в тех вер'
ru9 Russian Renedyn 2021-09-14 09:23:05 95
ru8 Russian Renedyn 2021-09-14 08:59:04 4 Мелкая правка: ' значение d вершинt, для сумм' -> ' значение в вершине, для сумм'
ru7 Russian Renedyn 2021-09-14 08:50:16 1137 Мелкая правка: ' (красные), чтобы это исправить в тех в' -> ' (красные). Чтобы это учесть в тех в'
ru6 Russian Renedyn 2021-09-13 21:48:03 479 Мелкая правка: '075.png)\n\n\n\nСд' -> '075.png)\nТеперь запрос суммы. \n\n\n\nСд'
ru5 Russian Renedyn 2021-09-13 20:05:04 328 Мелкая правка: 'м $add[v] += x$. \n![ ' -> 'м $add[v] <+=> x$. \n![ '
ru4 Russian Renedyn 2021-09-13 19:10:20 68
ru3 Russian Renedyn 2021-09-13 19:08:40 337 Мелкая правка: 'а таблица n * m, поступаю' -> 'а таблица $n \cdo m$, поступаю'
ru2 Russian Renedyn 2021-09-13 17:16:04 530 Мелкая правка: 'Прибавить X' -> 'Прибавить _X_'
ru1 Russian Renedyn 2021-09-13 16:17:16 149 Первая редакция (сохранено в черновиках)