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 .

Edit from another editorial author: You can solve it in .

• commented on Feb. 22, 2023, 12:17 a.m. edit 2

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 to where is the rightmost column of the triangle and is bottom row. To insert the diagonals, perform BIT update operation on all such that for from to . 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 , 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 and 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.

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

In case you are curious or are having trouble passing with the solution due to TLE (this sub barely passes with a 0.983s worst case), the 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 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.

• 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?

• 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.