I couldn't find this particular approach in existing editorials, so I decided to share it.↵
1. Problem↵
----------↵
You are given a 2D table $a$ with $n$ rows and $m$ columns. You need to answer $q$ queries offline.↵
Each query is four integers $x_1$ $y_1$ $x_2$ $y_2$ describing a rectangle.↵
For each query, you need to output ↵
↵
$$\sum_{i=x_1}^{x_2} (\max_{j=y_1}^{y_2} a_{i, j})$$↵
[cut]↵
2. How to Approach the Solution↵
--------------------------------↵
If we calculate the maximum for each row separately for every query, we get $O(qmn)$. We can build a Sparse Table for each row and find each maximum in $O(1)$. This reduces the total complexity to $O(mn\log(m) + qn)$. However, we can do better.↵
3. Removing Maximums from the Query↵
--------------------------------↵
Let's create new table $b$ with $n$ rows and $m$ columns.↵
↵
$$↵
b_{i,j}=↵
\begin{cases}↵
\max_{k=0}^{j}(a_{i,k}) - \max_{k=0}^{j-1}(a_{i,k}), & j \ne 0,\\↵
a_{i,j}, & j = 0.↵
\end{cases}↵
$$↵
↵
Now, if a query has $y_1 = 0$, its answer is simply↵
↵
$$↵
\sum_{i=x_1}^{x_2} \sum_{j=0}^{y_2} b_{i, j}↵
$$↵
↵
Indeed, because ↵
↵
$$↵
\forall i \in [0,n-1],\quad↵
\sum_{j=0}^{y} b_{i,j}↵
=↵
\max_{k=0}^{y} a_{i,k}.↵
$$↵
↵
4. Moving the Left Border↵
------------------↵
The main problem now is updating $b_{i, j}$ when we move the left border from $y_1$ to $y_1+1$.↵
Let's consider one row separately and assume $y_1 = 0$, as the other cases are similar.↵
Now, let $a$ be a one-dimensional array. Let $c$ denote the array $b$ after moving the left border from $0$ to $1$.↵
↵
$$↵
b_i =↵
\begin{cases}↵
a_i, & i = 0,\\↵
\max\limits_{k=0}^{i} a_k - \max\limits_{k=0}^{i-1} a_k, & i > 0.↵
\end{cases}↵
$$↵
↵
$$↵
c_i =↵
\begin{cases}↵
0, & i < 1,\\↵
a_i, & i = 1,\\↵
\max\limits_{k=1}^{i} a_k - \max\limits_{k=1}^{i-1} a_k, & i > 1.↵
\end{cases}↵
$$↵
Let's define a one-dimensional array $right$, where $right_i$ is the index of the nearest element to the right that is greater than $a_i$. We can calculate the $right$ array using a monotonic stack.↵
Let's consider two cases: $a_1 \ge a_0$ and $a_1 < a_0$↵
The first case is easy. If $a_1 \ge a_0$, we only need to change two values in $b$:↵
↵
$$↵
b_0 \leftarrow 0,\qquad b_1 \leftarrow a_1.↵
$$↵
↵
The second case is harder. If $a_1 < a_0$↵
↵
$$↵
b_1 \leftarrow 0,↵
$$↵
↵
$$↵
b_{right_i} \leftarrow a_{right_i} - a_i,↵
\qquad↵
i = 1,\ right_1,\ right_{right_1},\ldots↵
$$↵
↵
while↵
$$↵
a_i < a_0.↵
$$↵
↵
Indeed, after removing $a_0$, the prefix maximum remains equal to $a_i$ until we reach the first element greater than $a_i$. Therefore, for every element $a_i < a_0$ on this chain, its next greater element $a_{right_i}$ becomes the position where the prefix maximum increases, so its new contribution is $a_{right_i} - a_i$.↵
↵
Once we reach an element $a_i > a_0$, all further values of $b$ remain unchanged, since $a_0$ was not the maximum anymore.↵
↵
Thus, we can update the representation for the new left border by following the chain of nearest greater elements.↵
5. Processing the Queries↵
-------------------------↵
We can now process all queries offline by sorting them by their left border $y_1$.↵
↵
Initially, we set $y_1=0$.↵
↵
and construct the corresponding array $b$. Then we process the queries in increasing order of $y_1$. Whenever we move the current left border from $y_1$ to $y_1+1$, we apply the updates described in the previous section to every row.↵
↵
After the current left border becomes equal to the left border of the query, the answer can be obtained as↵
↵
$$↵
\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} b_{i,j}.↵
$$↵
↵
Therefore, we need a data structure that supports point updates of $b_{i,j}$ and rectangle sum queries.↵
↵
We can use a two-dimensional Fenwick tree for this purpose. Every change of one value of $b$ is performed as a point update, while the answer to a query is obtained using four prefix sums.↵
↵
Thus, after sorting the queries by $y_1$, we maintain the correct representation of the prefix maximums for the current left border and answer every query independently.↵
↵
6. Complexity of Updating b↵
------------------↵
The only remaining question is how many changes we perform when moving the left border.↵
↵
Consider one row. When the left border is moved from $y_1$ to $y_1+1$, we follow the chain of nearest greater elements↵
↵
$$↵
i=y_1+1,\quad↵
i=right_{i},\quad↵
i=right_{i},\ldots↵
$$↵
while↵
$$↵
a_i < a_{y_1}.↵
$$↵
↵
So we need to take the contribution of these chains into account when analyzing the complexity. Let's prove that any two chains are disjoint. This will give us a total complexity of $O(m)$.↵
↵
Let $i$ and $j$ be the starting points of two chains, and assume that↵
$i < j$. Suppose, for contradiction, that $k$ is a common element of↵
the two chains.↵
↵
Since $k$ belongs to the chain starting at $i$, we have $a_i < a_k$.↵
↵
On the other hand, $k$ belongs to the chain starting at $j$. By the↵
definition of the chain, it is followed while $a_k < a_{j-1}$. Therefore, $a_{j-1} > a_k$.↵
↵
But since $i < j$, the element $a_k$ is a maximum of the segment↵
$[i,k]$, which contains $a_{j-1}$. Therefore, $a_k \ge a_{j-1}$ which contradicts $a_{j-1} > a_k$.↵
↵
Since all elements of the chains are indices in the range $[0,m-1]$,↵
and the chains are pairwise disjoint, the total number of updated↵
indices in $b$ is $O(m)$.↵
↵
7. Complexity↵
------------------↵
Let's analyze the complexity.↵
↵
For every row, moving the left border requires following a chain of nearest greater elements. Each element can be processed only when it is reached by this procedure, so the total number of such updates over the whole process is linear in the number of elements of the row.↵
↵
As shown in the previous section, the total number of updates to $b$ is↵
↵
$$↵
O(nm).↵
$$↵
↵
Using a two-dimensional Fenwick tree, each point update and each prefix-sum query takes↵
↵
$$↵
O(\log n\log m).↵
$$↵
↵
Hence, maintaining $b$ takes↵
↵
$$↵
O(nm\log n\log m).↵
$$↵
↵
Each rectangle query requires four prefix sums, so all $q$ queries take↵
↵
$$↵
O(q\log n\log m).↵
$$↵
↵
The total complexity is therefore↵
↵
$$↵
\boxed{↵
O(nm\log n\log m + q(\log q + \log n\log m))↵
}.↵
$$↵
↵
The memory complexity is↵
↵
$$↵
\boxed{O(nm+q)}.↵
$$↵
↵
**Update:** This approach can also be extended to online queries using a↵
Fenwick tree over the rows with a persistent segment tree inside each↵
node. We can keep a separate version for every possible left border↵
$y_1$, allowing queries to be answered in arbitrary order.↵
↵
8. Usage↵
---------↵
↵
[This problem](https://codeforces.me/contest/2206/problem/E) can be↵
solved using this idea. Moreover, the same idea allows us to simplify↵
the solution to a one-dimensional Fenwick tree.↵
↵
This solution achieves a better time complexity than the one presented↵
in the editorial.
1. Problem↵
----------↵
You are given a 2D table $a$ with $n$ rows and $m$ columns. You need to answer $q$ queries offline.↵
Each query is four integers $x_1$ $y_1$ $x_2$ $y_2$ describing a rectangle.↵
For each query, you need to output ↵
↵
$$\sum_{i=x_1}^{x_2} (\max_{j=y_1}^{y_2} a_{i, j})$$↵
[cut]↵
2. How to Approach the Solution↵
--------------------------------↵
If we calculate the maximum for each row separately for every query, we get $O(qmn)$. We can build a Sparse Table for each row and find each maximum in $O(1)$. This reduces the total complexity to $O(mn\log(m) + qn)$. However, we can do better.↵
3. Removing Maximums from the Query↵
--------------------------------↵
Let's create new table $b$ with $n$ rows and $m$ columns.↵
↵
$$↵
b_{i,j}=↵
\begin{cases}↵
\max_{k=0}^{j}(a_{i,k}) - \max_{k=0}^{j-1}(a_{i,k}), & j \ne 0,\\↵
a_{i,j}, & j = 0.↵
\end{cases}↵
$$↵
↵
Now, if a query has $y_1 = 0$, its answer is simply↵
↵
$$↵
\sum_{i=x_1}^{x_2} \sum_{j=0}^{y_2} b_{i, j}↵
$$↵
↵
Indeed, because ↵
↵
$$↵
\forall i \in [0,n-1],\quad↵
\sum_{j=0}^{y} b_{i,j}↵
=↵
\max_{k=0}^{y} a_{i,k}.↵
$$↵
↵
4. Moving the Left Border↵
------------------↵
The main problem now is updating $b_{i, j}$ when we move the left border from $y_1$ to $y_1+1$.↵
Let's consider one row separately and assume $y_1 = 0$, as the other cases are similar.↵
Now, let $a$ be a one-dimensional array. Let $c$ denote the array $b$ after moving the left border from $0$ to $1$.↵
↵
$$↵
b_i =↵
\begin{cases}↵
a_i, & i = 0,\\↵
\max\limits_{k=0}^{i} a_k - \max\limits_{k=0}^{i-1} a_k, & i > 0.↵
\end{cases}↵
$$↵
↵
$$↵
c_i =↵
\begin{cases}↵
0, & i < 1,\\↵
a_i, & i = 1,\\↵
\max\limits_{k=1}^{i} a_k - \max\limits_{k=1}^{i-1} a_k, & i > 1.↵
\end{cases}↵
$$↵
Let's define a one-dimensional array $right$, where $right_i$ is the index of the nearest element to the right that is greater than $a_i$. We can calculate the $right$ array using a monotonic stack.↵
Let's consider two cases: $a_1 \ge a_0$ and $a_1 < a_0$↵
The first case is easy. If $a_1 \ge a_0$, we only need to change two values in $b$:↵
↵
$$↵
b_0 \leftarrow 0,\qquad b_1 \leftarrow a_1.↵
$$↵
↵
The second case is harder. If $a_1 < a_0$↵
↵
$$↵
b_1 \leftarrow 0,↵
$$↵
↵
$$↵
b_{right_i} \leftarrow a_{right_i} - a_i,↵
\qquad↵
i = 1,\ right_1,\ right_{right_1},\ldots↵
$$↵
↵
while↵
$$↵
a_i < a_0.↵
$$↵
↵
Indeed, after removing $a_0$, the prefix maximum remains equal to $a_i$ until we reach the first element greater than $a_i$. Therefore, for every element $a_i < a_0$ on this chain, its next greater element $a_{right_i}$ becomes the position where the prefix maximum increases, so its new contribution is $a_{right_i} - a_i$.↵
↵
Once we reach an element $a_i > a_0$, all further values of $b$ remain unchanged, since $a_0$ was not the maximum anymore.↵
↵
Thus, we can update the representation for the new left border by following the chain of nearest greater elements.↵
5. Processing the Queries↵
-------------------------↵
We can now process all queries offline by sorting them by their left border $y_1$.↵
↵
Initially, we set $y_1=0$.↵
↵
and construct the corresponding array $b$. Then we process the queries in increasing order of $y_1$. Whenever we move the current left border from $y_1$ to $y_1+1$, we apply the updates described in the previous section to every row.↵
↵
After the current left border becomes equal to the left border of the query, the answer can be obtained as↵
↵
$$↵
\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} b_{i,j}.↵
$$↵
↵
Therefore, we need a data structure that supports point updates of $b_{i,j}$ and rectangle sum queries.↵
↵
We can use a two-dimensional Fenwick tree for this purpose. Every change of one value of $b$ is performed as a point update, while the answer to a query is obtained using four prefix sums.↵
↵
Thus, after sorting the queries by $y_1$, we maintain the correct representation of the prefix maximums for the current left border and answer every query independently.↵
↵
6. Complexity of Updating b↵
------------------↵
The only remaining question is how many changes we perform when moving the left border.↵
↵
Consider one row. When the left border is moved from $y_1$ to $y_1+1$, we follow the chain of nearest greater elements↵
↵
$$↵
i=y_1+1,\quad↵
i=right_{i},\quad↵
i=right_{i},\ldots↵
$$↵
while↵
$$↵
a_i < a_{y_1}.↵
$$↵
↵
So we need to take the contribution of these chains into account when analyzing the complexity. Let's prove that any two chains are disjoint. This will give us a total complexity of $O(m)$.↵
↵
Let $i$ and $j$ be the starting points of two chains, and assume that↵
$i < j$. Suppose, for contradiction, that $k$ is a common element of↵
the two chains.↵
↵
Since $k$ belongs to the chain starting at $i$, we have $a_i < a_k$.↵
↵
On the other hand, $k$ belongs to the chain starting at $j$. By the↵
definition of the chain, it is followed while $a_k < a_{j-1}$. Therefore, $a_{j-1} > a_k$.↵
↵
But since $i < j$, the element $a_k$ is a maximum of the segment↵
$[i,k]$, which contains $a_{j-1}$. Therefore, $a_k \ge a_{j-1}$ which contradicts $a_{j-1} > a_k$.↵
↵
Since all elements of the chains are indices in the range $[0,m-1]$,↵
and the chains are pairwise disjoint, the total number of updated↵
indices in $b$ is $O(m)$.↵
↵
7. Complexity↵
------------------↵
Let's analyze the complexity.↵
↵
For every row, moving the left border requires following a chain of nearest greater elements. Each element can be processed only when it is reached by this procedure, so the total number of such updates over the whole process is linear in the number of elements of the row.↵
↵
As shown in the previous section, the total number of updates to $b$ is↵
↵
$$↵
O(nm).↵
$$↵
↵
Using a two-dimensional Fenwick tree, each point update and each prefix-sum query takes↵
↵
$$↵
O(\log n\log m).↵
$$↵
↵
Hence, maintaining $b$ takes↵
↵
$$↵
O(nm\log n\log m).↵
$$↵
↵
Each rectangle query requires four prefix sums, so all $q$ queries take↵
↵
$$↵
O(q\log n\log m).↵
$$↵
↵
The total complexity is therefore↵
↵
$$↵
\boxed{↵
O(nm\log n\log m + q(\log q + \log n\log m))↵
}.↵
$$↵
↵
The memory complexity is↵
↵
$$↵
\boxed{O(nm+q)}.↵
$$↵
↵
**Update:** This approach can also be extended to online queries using a↵
Fenwick tree over the rows with a persistent segment tree inside each↵
node. We can keep a separate version for every possible left border↵
$y_1$, allowing queries to be answered in arbitrary order.↵
↵
8. Usage↵
---------↵
↵
[This problem](https://codeforces.me/contest/2206/problem/E) can be↵
solved using this idea. Moreover, the same idea allows us to simplify↵
the solution to a one-dimensional Fenwick tree.↵
↵
This solution achieves a better time complexity than the one presented↵
in the editorial.
