Two-dimensional segment tree (with group modification of elements)

Preface and Problem Statement

I think many readers of this site have heard of such a useful structure as a segment tree. And if not, then about him on the Internet you can find a lot of interesting material ( here , articles on Habré: one and two times , google, finally).
Here I will analyze the generalization of the tree of segments into a two-dimensional case, and (unlike this article ) I will consider the implementation of the tree with the support of group modification of elements.

In general, in many cases it is possible to do without a tree of segments in general, for example, to use the Fenwick tree — it is written much lighter than the tree of segments, it has a smaller constant, and obviously extends to larger dimensions. But it has at least two minuses: it implements only reversible operations (to make it count the minimum / maximum will have to be considerably distorted, and even then it will not give full freedom of action (in the modification with the maximum - only increase the value, not decrease, with the minimum - on the contrary )) and does not support group modification of elements.

A good SQRT decomposition with a tricky selection of the block length will also sometimes help, but still you can’t compare it with the power of the segment tree.

So, the task.
')
There is an NxM field, you need to perform two types of queries:

1. Change cell values ​​with coordinates that satisfy the conditions x1 <= x <= x2, y1 <= y <= y2 to val
2. Calculate the value of a certain function (associative binary operation) from cells with coordinates that satisfy the conditions x1 <= x <= x2, y1 <= y <= y2

Here I will describe the implementation of the solution to the problem, where the function is the sum. I will say right away that I reached this decision myself (for about 15 hours), so I do not rule out the existence of a simpler one, and I will even be happy to hear it.

Tree structure

According to the structure, a two-dimensional segment tree represents a segment tree of segment trees (at each node of a tree of depth X_DEPTH there is an “nested” tree of depth Y_DEPTH). Hereafter, the depth of the tree is the binary logarithm of the number of elements it can accommodate. For example, the figure shows a tree of depth 1, each node of which contains a tree of depth 2. Such a tree can process requests of the form [x1; x2] ⊆ [0; 1], [y1; y2] ⊆ [0; 3].

We enumerate the vertices of these trees (both external and all nested) as ordinary one-dimensional trees.
Then each vertex of the nested one will be characterized by the coordinate [x] [y], x is the number of the vertex of the outer tree in which it is located, y is the inner one.

By sector we mean a rectangle formed by the cells x1 <= x <= x2, y1 <= y <= y2. Then each vertex of the nested subtree is responsible for a certain sector.

In each node of the “nested” tree, we will store four parameters:

• add - the amount by which the result should be increased when requesting an amount on nested sectors (descendants along the xth and yth coordinates)
• add_x - the value by which the result should be increased when requesting a sum on incompletely nested segments (descendants along the y-th coordinate, but with the same x-th)
• add_y - the value by which the result should be increased when requesting a sum on incompletely nested segments (descendants of the xth coordinate, but from the same yth)
• value - the sum in the subtree of the vertex (not counting the additions listed above)

In computer memory, as it is easy to understand, this information will be represented by four two-dimensional arrays.

Preprocessing operations

When we perform a modification operation, as in the one-dimensional case, we will only change the values ​​of the list of vertices defined for this sector. When summing up on the same sector, we will turn to the same vertices.

If we change the value of the vertex [x0] [y0], which is responsible for the sector [x0_1; x0_2] [y0_1; y0_2], it is not difficult to understand that all sectors that include this sector can be found as pairs (x; y): x1 <= x0_1 AND x0_2 <= x2 AND y1 <= y0_1 AND y0_2 <= y2. that is, it suffices to collect a set of X x-s, Y for y-s, and then iterate through all pairs from XxY.
Well, to collect these same lists, you need to go through the vertices, as is the case with a query on a one-dimensional tree.

Considering a particular pair (x; y), one can easily calculate xl, xr, yl, yr — the boundaries of the section of the current vertex, and also xc and yc — the numbers of elements at the intersections along the x-axis and y-axis axes.

Modification operation

1. If the request completely includes the sector of the current vertex, then you need to add to the add vertices a change val (to all descendants both on the x-th and y-th you need to add val):
   add + = val;
   
2. If the request includes the current sector only on the xth coordinate, change the add_y:
   add_y + = val * xc;
   
3. If the request includes the current sector only for the y-th coordinate, change the add_x:
   add_x + = val * yc;
   
4. If the request does not include a sector at all:
   value + = val * xc * yc;
   

With add, I think everything is clear (see the one-dimensional case).

When the request includes the current sector in the y-th coordinate, then in the y-th there may be descendants that will not be affected in this request, but will be in the future if the amount is requested. That's why we increase add_x.
Similar with add_y.

And, finally, if none of the three previous conditions is met, then the environments of direct descendants of a given vertex will change, and the second will not. Consequently, this change should be taken into account, but not spread further. Increase value.

Summation operation

Let us denote by res the result of the query, which we will calculate. In addition to preprocessing, let's calculate the bounds of that part of the query that we are looking for at a given vertex (the bounds of the required part):

xvl = max (xl, x1), xvr = min (xr, x2), yvl = max (yl, y1), yvr = min (yr, y2)

1. We need to add to all the request cells in the current sector add the current vertex:
   res + = add * xc * yc;
   
2. If the sought-for part is equal to the vertex sector in the x-th range:
   res + = add_x * yc;
   
3. If the required part is equal to the vertex sector in the y-range:
   res + = add_y * xc;
   
4. If the sector of the current vertex is entirely in the query (we will not go down below):
   res + = value;
   

Asymptotics

As can be seen from the description, this solution will work for O (N * X_DEPTH * Y_DEPTH), where N is the number of requests.

Implementation

The implementation of this solution can be found at http://dl.dropbox.com/u/3693476/articles/segtree2d/segtree2d.cpp (the file is a solution to the Farm problem, D from the file http://dl.dropbox.com/u/ 3693476 / articles / segtree2d / problems01.pdf ). If you want to get tests for this problem, in order to debug your decision, write your request to my mailbox george.agapov@gmail.com.

PS Thank you all for your attention, I hope this article will be useful to someone.