I saw the following problem some time ago in a Russian Olympiad:

You are given $$$N$$$ $$$(1 \leq N \leq 10^4)$$$ integers in an array $$$(-10^9 \leq a_i \leq 10^9)$$$. There are Q queries that need to be answered online: — What is the minimum absolute difference of any two numbers in the range $$$[L, R]$$$?

Constraints:

• $$$(1 \leq N \leq 10^4)$$$
• $$$(1 \leq Q \leq 10^5)$$$
• $$$(-10^9 \leq a_i \leq 10^9)$$$
• $$$(1 \leq L \leq R \leq N)$$$

If anyone can give a hint or a solution, it would be greatly appreciated. I don't have a link to the original problem, if anyone has it, please put it in the comments.

I was thinking about SQRT decomposition and Segment trees, but you can't merge blocks/nodes easily. Also, using persistent segment trees doesn't really work for ranges, other than prefixes. Any ideas?

Edit: I solved it using SQRT decomposition. Solution