Editorial for CCC '19 S5 - Triangle: The Data Structure

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Right-align the 2D array. If we iterate over the 2D array in increasing size order of minor diagonal, insert those values into a 2D max-BIT, we can query the bottom-right corner of a triangle the moment we have inserted all of the values in the given triangle into the 2D BIT, assuming the default values are otherwise zero. This approach is $\mathcal{O}(N^2 \log^2 N)$ ~\mathcal{O}(N^2 \log^2 N)~.

Edit from another editorial author: You can solve it in $\mathcal{O}(N^2 \log K)$ ~\mathcal{O}(N^2 \log K)~.

Comments

2
31501357 commented on Feb. 22, 2023, 12:17 a.m. ← edit 3 →
If anyone is confused, minor diagonal is bottom left to top right, or a1-h8 diagonal for chess. The query you want to do is the rectangle from $(0, 0)$ ~(0, 0)~ to $(x, y)$ ~(x, y)~ where $x$ ~x~ is the rightmost column of the triangle and $y$ ~y~ is bottom row. To insert the diagonals, perform BIT update operation on all $A[i][j]$ ~A[i][j]~ such that $i+j=m$ ~i+j=m~ for $m$ ~m~ from $2n-2$ ~2n-2~ to $n$ ~n~. You MUST make the query IMMEDIATELY after inserting the last diagonal of a subtriangle, otherwise, the query will contain numbers outside the subtriangle you wish to query.

For example.

4 2 3 1 2 4 2 1 6 1 4 2

After inserting the bottom right subtriangle.

0 0 0 0 0 0 0 0 0 0 0 1 0 0 4 2

Query $(0, 0)$ ~(0, 0)~, $(3, 3)$ ~(3, 3)~ before inserting anything else.

After inserting the next diagonal.

0 0 0 0 0 0 0 2 0 0 2 1 0 1 2 4

Immediately query $(0, 0, 2, 3)$ ~(0, 0, 2, 3)~ and $(0, 0, 3, 2)$ ~(0, 0, 3, 2)~ before inserting the next diagonal.

Edit: You need a corner at the bottom right since for a MAX binary indexed tree, there is no inverse operation as opposed to a SUM BIT, so you the origin must be the corner for any query.

Edit 2: Zero is the default value because it's smaller than any possible input value, of course if the input contained negative numbers you'd fill the matrix with something like -99999999. This is so they don't affect the queries, and so that performing the BIT update operation actually inserts the input number into the BIT. Also some modifications above.

6

Nils_Emmenegger commented on Sept. 11, 2021, 7:50 p.m.

In case you are curious or are having trouble passing with the $\mathcal{O}(N^2\log^2 N)$ ~\mathcal{O}(N^2\log^2 N)~ solution due to TLE (this sub barely passes with a 0.983s worst case), the $\mathcal{O}(N^2\log K)$ ~\mathcal{O}(N^2\log K)~ mainly relies on the observation that the maximum element of a sub-triangle of a certain size can be found by taking the maximum of three sub-triangles with sizes two-thirds of the one that we want to find. Thus, starting from sub-triangles of size 1, we can keep solving for sub-triangles that get about 50% bigger each time, allowing us to find the maximum elements in sub-triangles of the desired size in $\log K$ ~\log K~ steps.

Another way of going about it is observing that the maximum element of a sub-triangle of a certain size can be found by taking the maximum of two sub-triangles and one square whose sizes and side lengths respectively are half of the size of the sub-triangle we are trying to find.

Both methods personally remind me of the construction of sparse tables.

1

DynamicSquid commented on Feb. 16, 2022, 1:32 a.m.

Won't you be skipping numbers of a triangle if you increase the size of a triangle by more than 1 each time?

2

andy_zhu23 commented on Feb. 16, 2022, 1:45 a.m.

yes, but it doesn't matter, since you are able to get the maximum of each current triangle using the sub triangle 2/3 of the size of the current one anyway.