### steveonalex's blog

By steveonalex, 4 months ago, Hi guys, this is my first blog on Codeforces. So if there were any mistakes or suggestions, feel free to correct me down in the comment section. Anyway, I discovered a nice way to solve static range query problems using "Divide and conquer", and I'm eager to share it with you guys.

Pre-requisites:
• Prefix Sum.

## Problem 1:

Given an array $A$ of $N (N \leq 10^{5})$ integers, your task is to answer $q (q \leq 10^{5})$ queries in the form: what is the minimum value in the range $[l, r]$?

For now, let's forget about Segment Tree, Square Decomposition, Sparse Table and such. There's a simple way to solve this problem without any use of these fancy data structure.

First, let's start with $L_{0} = 1$, $R_{0} = n$, and $M_{0} = \left\lfloor { \frac{L_{0} + R_{0}}{2} } \right\rfloor$. Let's just assume that every query satisfy $L_{0} \leq l \leq M_{0} < r \leq R_{0}$. We maintain two prefix sum arrays:
• $X[i] = min(A[i], A[i+1], ..., A[M_{0}-1], A[M_{0}])$
• $Y[i] = min(A[M_{0}+1], A[M_{0}+2], ..., A[i-1], A[i])$

The answer to the query $[ l_{0} , r_{0} ]$ is simply $min(X[l_{0}], Y[r_{0}])$. But what about those queries that doesn't satisfy the aforementioned condition? Well we can recursively do the same thing to $L_{1} = L_{0}, R_{1} = M_{0}$, and $L_{2} = M_{0} + 1, R_{2} = R_{0}$, hence the name "Divide and conquer". The recursive tree is $log N$ layers deep, each query exists in no more than $log N$ layers, and in each layer you do $O(N)$ operation. Therefore this algorithm runs in $O((N + q) * log N)$, and $O(N + q)$ memory.

## So... Why on earth should I use it?

While this technique has practically the same complexity as Segment Tree, there is an interesting property: You only perform the "combine" operation once per query. Here's a basic example to show how this property can be exploited.

## Problem 2:

Define the cost of a set the product of its elements. Given an array $A$ of $N (N \leq 2*10^{5})$ integers and a positive integer $k$ ($k \leq 20$). Define $g(l, r, k)$ as sum of cost of all subsets of size $k$ in the set {$A[l], A[l+1], ..., A[r-1], A[r]$}. your task is to answer $q (q \leq 5 * 10^{5})$ queries in the form: what is $g(l, r, k)$ modulo $10^{9} + 69$?.

Naive Idea
Now I'll assume that you've read the naive idea above (you should read it). Notice how combining the value of two ranges runs in $O(k^2)$. However, if one of the two ranges has the length of $1$, then they can be combined in $O(k)$. This means a prefix-sum can be constructed in $O(N * k)$.
Why is this important? Let's not forget that in the naive Segment Tree idea, the bottle-neck is the convolution calculation, and we wish to reduce that in exchange for less expensive operations, which is what our aforementioned divide & conquer technique can help with, since you only do the expensive "combine" operation once per query. And besides, unlike Segment Tree, you can calculate the answer right away using the formula $\sum_{t=1}^k X[l][t] * Y[r][k - t]$

This will runs in $O(N * log N * k + q * (k + log N))$, and $O(N + q + k)$ memory, which is much better than the Segment Tree idea.

## Related problem:

Vietnamese problems:
MofK Cup Round 1 — E: Xor Shift
• Contest Link: DHBB 2023 Upsolve Contest; Problem Link: DHBB — 11th Grader Division — Problem 3: HKDATA (click on the link and join the contest, then click on the problem link)

English problems:
USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences  Comments (15)
 » Auto comment: topic has been updated by steveonalex (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 4 →   https://codeforces.com/blog/entry/57046This technology is faster than yours. And the scope is same.
•  » » 4 months ago, # ^ | ← Rev. 2 →   Well, no. The whole point of the D&C algorithm is to reduce the amount of time you have to perform the expensive "combine" operation, and sadly Sqrt-Tree didn't fit this niche very well. • In the preprocessing process, Sqrt-Tree requires storing 3 arrays in each layers, therefore it is barely even faster than an $O(N * log N)$ preprocessing for any practical $N$ at all, not to mention that Sqrt-Tree has to call a lot of "combine" function, so that's even worse. In problems where "combine" operation is much more expensive than doing a prefix sum, Sqrt-Tree quickly falls apart. • In each query, Sqrt-Tree have to perform the "combine" operation 2 times, while the number for the D&C algorithm is only 1. So yeah, these two techniques don't have the same scope.
 » Auto comment: topic has been updated by steveonalex (previous revision, new revision, compare).
 » isnt the time complexity ends in n* k^2 * logn either way , like you lose the logn factor since you do merging only once but you get it again since you do d&q so what is the point. And idk imo the best algorithm if the operation is prefix summable is fenwick tree which is low on the constant factor and super easy to implement.
•  » » 4 months ago, # ^ | ← Rev. 3 →   It's not, you will call merge function exactly Q times. This technique doesn't require the operation to be prefix summable (sorry, I meant that you don't need this \begin{gather} res_{[l,r]} = pref[r] — pref[l-1] \end{gather} or \begin{gather} res_{[l,r]} = pref[r] \quad\text{op}\quad \text{easy_to_compute_inverse}(pref[l-1]) \end{gather} property, but operation of course need to be prefix summable)
•  » » » yeah I just checked and saw I missed N * logN * k^2 -> N * logN * k and q * logN * k^2 -> q * k^2 + q * logN , it makes sense that it is faster.
 » I think the space complexity should be O(N log N) instead of O(N+q).
•  » » These arrays in this algorithms doesn't need to co-exists, therefore if you do some careful clean up then the space complexity should be $O(N + q)$. That helps in some problems whose memory limit is super masochistic.
•  » » » Oh I got it, thanks
 » USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences (one of the solutions uses this technique)
•  » » 4 months ago, # ^ | ← Rev. 3 →   Thank you! Appreciate it :DD
 » 4 months ago, # | ← Rev. 3 →   The answer to the query [l0,r0] is simply min(X[l0],Y[r0]). But what about those queries that doesn't satisfy the aforementioned condition? Well we can recursively do the same thing to L1=L0,R1=M0, and L2=M0+1,R2=R0, hence the name "Divide and conquer". The recursive tree is logN layers deep, each query exists in no more than logN layers, and in each layer you do O(N) operation. Therefore this algorithm runs in O((N+q)∗logN), and O(N+q) memory. Can you shed some more light on how the memory is O(N+q), what is being stored exactly ? If we cache the intermediate results then overall memory should be O(NlogN) and then it's same as segtree.
•  » » In my knowledge, space complexity stands for how much memory that is being allocated at the same time. Notice how these prefix sum array in each procedure doesn't have to co-exists, therefore if you clear these arrays after you are done with the procedure, the memory are still $O(N + q)$. Oh and btw Segment Tree space complexity is $O(N)$
 » Isn't the final complexity O(N * log N * k + q * (k + log N))? When you combine two ranges in your final approach, you only need to calculate the DP value for subsets of size k (unlike with segment tree).