This time I will explain about a problem that I managed to get the idea to solve, but didn’t have time to code at the contest. It is the Snackdown 2016 Elimination Round - SEGSUMQ “Yet Another SubSegment Sum Problem”.
In this problem, we will be given 2 arrays of size $N$: $A$ and $B$. We will also be given $Q$ queries in the form: $(L, R, C, D)$. We need to compute sum of max($0$, $A_iC - B_iD$) for all $i$ from $L$ to $R$. We must answer all of those queries online.
My solution is different from the solution explained in the editorial. I think I must try to solve the problem using the editorial’s solution later.
To solve this problem, in range $L..R$ we only need to consider indices $i$ where $A_iC \ge B_iD \rightarrow \frac{D}{C} \le \frac{A_i}{B_i}$. So what do we need to solve this kind of problem?
Simpler version:
Given an array $A$ of size $N$. We need to know how many elements in array $A$ from $L$ to $R$ whose value is greater than $X$. Remember that we will answer $Q$ such queries and we need to do it online.
We will use a data structure called Range Tree. Usually I assume that range tree is a segment tree whose nodes are another data structures, they can be sets, vectors, AVLs, etc. but in this case I use vectors.
So, in a node covering range $i..j$, there will be a vector containing elements $A_i, A_{i+1}, \dots, A_j$. It’s like segment tree, we will need to compute answer in each interval only when necessary. In this case, in nodes that cover interval $L..R$, we need to know how many of them are greater than $X$. The next part is: Given an array of integers, how many of them are greater than or equal to $X$?
If we need to do it many times, usually we sort the array, and yes, we use binary search. In our case, we need to maintain each vector in sorted order. It is obvious that intervals which cover only one element (nodes that are leaves) will have the vector sorted, but what about the other intervals? We can use merge routine like we do it in merge sort to merge two sorted arrays become one sorted array.
Now, we have got the basic idea. So, to make the range tree, we build the “segment tree”’s nodes using merge (except leaves), and for each query we do binary search(es) on nodes traversed like usual segment tree.
Both the time and memory complexity for building the range tree is $O(N \lg N)$. To answer each query, we need $O(\lg^2 N)$, so the total time complexity is $O(N \lg N + Q \lg^2 N)$.
To solve SEGSUMQ, we need to modify the values stored in each node. But the basic idea is the same as the simpler problem above. My solution for SEGSUMQ can be accessed «here» (from Codechef submission).