Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

Shortest Subarray With Sum at Least K: A Monotonic Stack + Binary Search Approach
Разница между en2 и en3, 1661 символ(ов) изменены
# Shortest Subarray With Sum at Least $$$K$$$: An $$$O(n\log n)$$$ Solution Using a Monotonic Stack and Binary SearchThe standard solution uses a monotonic deque and runs in $$$O(n)$$$.↵
↵
This post describes an alternative $$$O(n\log n)$$$ approach. We maintain the useful prefix sums in a monotonic vector and binary search over it.↵
↵
The idea followcomes from two observations:↵
↵
*- A smaller prefix sum is better.↵
*- Among feasible prefix sums, a later index is better.↵
↵
---↵
↵
## Prefix-s Sum fFormulation↵
↵
Let↵
↵
$$$↵
P_0=0,\qqua $P_0=0$ and $P_i=a_1+a_2+\cdots+a_i$.↵
$$$↵
↵
The sum of the subarray from $$$j+1$$$ to $$$i$$$ is↵
↵
$$$↵
i$ is $P_i-P_j$.↵
$$$↵
↵
We require↵
↵
$$$↵
 $P_i-P_j\geq K,↵
$$$↵
↵
$, or equivalently,↵
↵
$$$↵
P_j\leq P_i-K$.↵
$$$↵
↵
Thus↵
Therefore, for every right endpoint $$$i$$i$, we need the largest index $$$j<i$$$ satisfying↵
↵
$$$↵
 $P_j\leq P_i-K.↵
$$$$.↵
↵
Choosing the largest valid $$$j$$j$ minimizes the length $$$i-j$$$.↵
↵
---.↵
↵
## Removing dDominated pPrefix sSums↵
↵
Suppose↵
↵
$$$↵
x<y↵
$$$↵
↵
and↵
↵
$$$↵
 $x<y$ and $P_y\leq P_x.↵
$$$$.↵
↵
Then prefix index $$$x$$x$ is never useful again.↵
↵
For any future endpoint $$$i$$$, if↵
↵
$$$↵
P_i-P_x\geq K,↵
$$$↵
↵
then, because $$$P_y\leq P_x$$$,Indeed, if $P_i-P_x\geq K$, then↵
↵
$$$↵
P_i-P_y\geq P_i-P_x\geq K.↵
$$$$,↵
↵
because $P_y\leq P_x$.↵
↵
Moreover,↵
↵
$$$↵
i-y<i-x.↵
$$$↵
↵
Therefore, whenever $$$x$$$ is valid, $$$y$$$ is also valid and $i-y<i-x$, so using $y$ always gives a shorter subarray.↵
↵
Hence, whenever a new prefix sum arrives, every previous prefix sum greater than or equal to it can be removed permanently.↵
↵
```cpp↵
while (!a.empty() && a.back().first >= p[i]) {↵
    a.pop_back();↵
}↵
a.push_back({p[i], i});↵
```↵
↵
After every insertion, the stored pairs satisfy↵
↵
$$$↵
P_{j_1}<P_{j_2}<\cdots<P_{j_m}↵
$$$↵
↵
and↵
↵
$$$↵
j_1<j_2<\cdots<j_m$.↵
$$$↵
↵
Thus, the vector is increasing in both prefix sum and index.↵
↵
---↵
↵
## Binary sSearch↵
↵
For the current endpoint $$$i$$i$, define↵
↵
$$$↵
 $T=P_i-K$.↵
$$$↵
↵
We need the last stored pair whose prefix sum is at most $$$T$$T$.↵
↵
Since the prefix sums are increasing, all valid pairs form a prefix of the vector.↵
↵
 Since the indices are also increasing, the last valid pair has the largest valid index.↵
↵
Therefore, we use:↵
↵
```cpp↵
int pos = upper_bound(↵
    a.begin(),↵
    a.end(),↵
    make_pair(p[i] - k, i)↵
) - a.begin() - 1;↵
```↵
↵
Searching for↵
↵
$$$↵
\left(P_i-K,\ i\right)↵
$$$↵
↵
 $(P_i-K,i)$ finds the last stored pair satisfying↵
↵
$$$↵
 $P_j\leq P_i-K$.↵
$$$↵
↵
---↵
↵
## Correctness proof↵
↵
### Lemma 1↵
↵
If $$$x<y$$$ and $$$P_y\leq P_x$$$, then prefix index $$$x$$x$ can be removed permanently after processing $$$y$$$.↵
↵
### **Proof.**↵
↵
Whenever $$$x$$x$ forms a valid subarray with a future endpoint $$$i$$$, we have↵
↵
$$$↵
P_i-P_x\geq K.↵
$$$↵
↵
Sinci$, the index $y$ also forms a valid subarray because $$$P_y\leq P_x$$$,↵
↵
$$$↵
P_i-P_y\geq P_i-P_x\geq K.↵
$$$↵
↵
Thus, $$$y$$$ is also valid. .↵
↵
Since $$$y>x$$$,↵
↵
$$$↵
i-y<i-x.↵
$$$↵
↵
, we have $i-y<i-x$. Therefore, $$$y$$y$ always gives a shorter subarray than $$$x$$$. Hence $$$x$$, so $x$ can never be optimal again. $$$\square$$$↵
↵
### Lemma 2↵
↵
The maintained vector is strictly increasing in both prefix sums and indices.↵
↵
### **Proof.**↵
↵
Indices are inserted from left to right, so their order is increasing.↵
↵
. Before inserting $$$P_i$$$a new prefix sum, every suffix element whose prefix sum is at least $$$P_i$$$whose value is greater than or equal to it is removed. Therefore, the prefix sums alsoHence both coordinates remain strictly increasing. $$$\square$$$↵
↵
### Theorem↵
↵
For every endpoint $$$i$$i$, binary search returns the shortest valid subarray ending at $$$i$$i$.↵
↵
### **Proof.**↵
↵
All feasible stored prefix sums satisfying↵
↵
$$$↵
P_j\leq P_i-K↵
$$$↵
↵
form a prefix of the vector.↵
↵
 Binary search returns the finallast element of this prefix. Since the indices are increasing, this element has the largest valid index and therefore minimizes $$$i-j$$$, which has the largest valid index.↵
↵
AnEvery removed prefix wais dominated by a later prefix according toby Lemma 1, so removing it cannot destroy an optimal answer.↵
↵
Taking the minimum over all endpoints therefore gives the globally shortest valid subarray. $$$\square$$$↵
↵
---↵
↵
## Implementation↵
↵
```cpp↵
for (int i = 0; i <= n + 1; i++) {↵
    while (!a.empty() && a.back().first >= p[i]) {↵
        a.pop_back();↵
    }↵
↵
    a.push_back({p[i], i});↵
↵
    if (i ==> 0) continue;↵
↵
{↵
        int pos1 = upper_bound(↵
            a.begin(),↵
            a.end(),↵
            make_pair(p[i] - k, i)↵
        ) - a.begin() - 1;↵
↵
        if (pos1 == -1) continue;↵
↵
        int l = a[p1].second;↵
        ans = min(ans, i - a[pos].second);l);↵
    }↵
}↵
```↵
↵
Here, `p` is the prefix- sum array, while `a` stores the non-dominated pairs↵
↵
$$$↵
\left(P_j,j\right).↵
$$$ $(P_j,j)$.↵
↵
Since the original problem has $$$K>0$$$, inserting $$$\left(P_i,i\right)$$(P_i,i)$ before querying cannot create a zero-length subarray, because↵
↵
$$$↵
answer because $P_i\not\leq P_i-K.↵
$$$↵
↵
---$.↵
↵
## Complexity↵
↵
Each prefix sum is inserted once and removed at most once. Therefore,, so all stack operations together take $$$O(n)$$$.↵
↵
We perform one binary search for every prefix sum, so the total running time is↵
↵
$$$↵
giving a total time complexity of $O(n\log n).↵
$$$$.↵
↵
The memory complexity is↵
↵
$$$↵
O(n).↵
$$$↵
↵
--- $O(n)$.↵
↵
## Final pPerspective↵
↵
The important object is not really a stack or a deque. It is the set of non-dominated prefix states.↵
↵
A state↵
↵
$$$↵
\left(P_x,x\right)↵
$$$↵
↵
is dominated by↵
↵
$$$↵
\left(P_y,y\right)↵
$$$↵
↵
whenever↵
↵
$$$↵
P_y\leq P_x↵
$$$↵
↵
and↵
↵
$$$↵
y>x.↵
$$$ $(P_x,x)$ is dominated by $(P_y,y)$ whenever $P_y\leq P_x$ and $y>x$.↵
↵
The second state is simultaneously:↵
↵
* easier to satisfy, because its prefix sum is smaller;↵
* better for minimizing the answer, because its index is later.↵
↵
Maintaining only non-dominated states creates a monotone frontier increasing in both prefix sum and index.↵
↵
The classical deque solution exploits the same dominance relation to obtain $$$O(n)$$$. This approach instead uses binary searches over the monotone frontier, giving a clean $$$O(n\log n)$$$ solution.↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский dtu1141b 2026-07-28 23:36:55 0 Tiny change: '\nThe standa' -> 'The standa'
en3 Английский dtu1141b 2026-07-28 23:35:09 1661 Tiny change: 'i], i});\n````\n\nAfter ' -> 'i], i});\n\nAfter ' (published)
en2 Английский dtu1141b 2026-07-28 23:29:22 2264
en1 Английский dtu1141b 2026-07-28 23:24:39 5384 Initial revision (saved to drafts)