What are 2D segment trees?
For the most part, 2D segment trees can be used to solve similar problems to the ones mentioned below.
Scenario: There is a 2D array where each cell has a value. Given values that define a rectangle, determine the sum of the values inside. Point changes or range changes may occur. (Static version of the problem:)
2D segment trees are expensive, but they are one of the best ways to solve this problem. A 2D segment tree is a segment tree of segment trees.
Solving the problem:
Setting up for queries:
The explanation for setting up queries is actually quite easy. For each row, generate a segment tree of the values inside that row.
Now it’s time to combine some of the segment trees together to make one big, massive segment tree. The plan is to make a new segment tree for rows 0–1 and 2–3. Segment trees are traditionally stored as an array, and it turns out that adding corresponding values to the tree produces a merged tree.
Now that the segment tree has been calculated for rows 0–1 and 2–3, it is time to combine them to create the segment tree for rows 0-4. The same process for combing segment trees is used again until a tree that covers all rows is created.
Doing Sum Queries:
It turns out this is really hard to explain with words. So, I made a visual representation. Since sum queries come in boxes, multiple different segment trees might need to be checked.
Doing Updates:
It turns out this is also really hard to explain with words. So, I made a visual representation. Since range queries are 2D in this problem, whenever a rectangle is updated, multiple different segment trees might be visited, so every value is represented.