Problem

There is are famous problem for given array of numbers and number $$$K$$$ find minimums for all segments of length $$$K$$$.

More general variant: for given array of size $$$n$$$ and $$$q$$$ queries $$$[l_i,r_i]$$$ need to find minimums on segmets at $$$l_i \leq l_{i+1}$$$ и $$$r_i \leq r_{i+1}$$$. Solution must be $$$O(n+q)$$$.

To solve this problem we need sliding window method, we numbers from segments is window. Needed data structure should be able to push_back (add number to the end of window), pop_front (remove first element) и get_min — current minimum in window.

I was surprised to find that there are two types of such data structure. First is very popular and can be easily found in web. But type that I use whole life I can't find. I'll describe both of them.

Solution #1

The idea is to store sequence of increasing minimums. First minimum is minimum of whole window, second is minimum of elements after first minimum, and so on. For example, for window [2,3,1,5,4,8,7,6,9] sequence is [1,4,6,9].

When element is adding to the right of window (incR, push_back), the sequence changes as follows: all higher elements are gone from sequence, new element is goes to the end of sequence.

Couple of samples for [1,4,6,9]:

Adding 5: [1,4,6,9] -> [1,4] -> [1,4,5]

Adding 100: [1,4,6,9] -> [1,4,6,9,100]

Adding 0: [1,4,6,9] -> [] -> [0]

In removing left element from window (incL, pop_front) we need to know if first element of sequence is first element of window. Impossible to know this only by values, so we need to store sequence of pairs (value, index) except of only values. Previous example turns to [(1,2), (4,4), (6,7), (9,8)], where indices are numbered from zero. Bounds of window stored as pair of numbers $$$L$$$ and $$$R$$$. So, if first element of sequence is first element of window, that is its index equals to $$$L$$$, than only needed is to remove this first element from sequence.

Realization requires data structure that can efficiently perform operations of removing elements from left and right and adding new element to the right. Here we can use deque (std::deque in c++).

int inf = 2e9;
struct sliding_window{
    deque<pair<int,int>> d;
    int l, r;
    
    sliding_window(){
        l = r = 0;
    }
    
    void push_back(int x){
        while(!d.empty() && d.back().first >= x) d.pop_back();
        d.emplace_back(x,r);
        ++r;
    }
    
    void pop_front(){
        if(d.front().second == l) d.pop_front();
        ++l;
    }
    
    int get_min(){
        return d.empty() ? inf : d.front().first;
    }
};

Solution #2

Represent window as two stacks: prefix of window stored in left stack $$$L$$$ so that first element of window in top of $$$L$$$, and suffix of window is stored in right stack $$$R$$$ so that last element of window in top of $$$R$$$.

[2,3,1,5,4,8,7,6,9]
<-------|--------->

L = [5,1,3,2]
R = [4,8,7,6,9]

When element is adding to the right of window (incR, push_back), it just goes to the top of $$$R$$$.

In removing left element from window (incL, pop_front), its pops from $$$L$$$, except of case when $$$L$$$ is empty. In this case we need to Тогда перед удалением происходит операция перебрасывания правого стека в левый: пока правый стек не закончится, его верхний элемент перемещается в левый стек. Например,

[4,3,1,2]
|------->

L = []
R = [4,3,1,2]

L = [2]
R = [4,3,1]

L = [2,1]
R = [4,3]

L = [2,1,3]
R = [4]

L = [2,1,3,4]
R = []

[4,3,2,1]
<-------|

Теперь, после перебрасывания, из левого стека можно удалять верхний элемент.

Чтобы отвечать в любой момент о текущем минимуме в окне нужно знать минимумы в стеках. Так как правый стек только увеличивается или очищается полностью, его минимум можно поддерживать в отдельной переменной $$$Rmin$$$.

В левом стеке вместо самих значений нужно хранить минимум среди значений от этого элемента до дна стека. Например для стека [5,7,3,4,2,1,8,6] это будет стек [5,5,3,3,2,1,1,1]

Итого, минимум в окне будет равен либо верхнему элементу левого стека, либо $$$Rmin$$$.

int inf = 2e9;
struct sliding_window{
    vector<int> l, r;
    int rmin;
    
    sliding_window(){
        rmin = inf;
    }
    
    void push_back(int x){
        r.push_back(x);
        rmin = min(rmin, x);
    }
    
    void pop_front(){
        if(l.empty()){
            for(int mn = inf; !r.empty();){
                mn = min(mn, r.back());
                l.push_back(mn);
                r.pop_back();
            }
            rmin = inf;
        }
        l.pop_back();
    }
    
    int get_min(){
        int res = rmin;
        if(!l.empty()) res = min(res, l.back());
        return res;
    }
};

Примечание

Оба решения работают за одинаковую ассимптотику. Второе считаю более простым для понимания как алгоритм, но в первом меньше кода. Про сравнительное время работы ничего не могу сказать.

Кстати, оба решения можно проапгрейдить до операции push_front, хотя кажется, такая операция нигде не нужна.