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$$$?.

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
Thanks for reading :-D

UPD1: adding an English problem, suggested by szaranczuk. UPD2: minor adjustments.