Neel Mishra
← All Posts
DSA Series · Trees · Fenwick Trees · Part 6

Counting Smaller Prefix Sums

June 2026 · 22 min read

I want to solve one tidy little problem in this post and then squeeze every drop of insight out of it: count how many earlier prefix sums are smaller than the current prefix sum. It looks like a toy, but it is the engine behind a surprising number of real questions, and it is the cleanest motivation I know for reaching past a plain prefix-sum array and picking up a Fenwick tree. By the end I will have a one-pass O(n log n) solution, an animation that walks through it value by value, a catalogue of sibling problems that share the same skeleton, and an honest comparison with the segment tree I deliberately chose not to use.

The Problem, Precisely

Let me fix notation. Given an array a[0..n-1], I build the prefix-sum array

P[0] = 0
P[k] = a[0] + a[1] + ... + a[k-1]   for k = 1..n

so there are n + 1 prefix sums, and P[0] = 0 is included on purpose. For each index i I want the count of earlier indices j < i with P[j] < P[i]. Summing that count over every i gives the total number of ordered pairs (j, i) with j < i and P[j] < P[i]. In plain words: the number of ascending pairs inside the prefix-sum array. That single number is what I am after.

Why I Care: Positive-Sum Subarrays

On its own "ascending pairs of prefix sums" sounds abstract, so here is the reduction that makes me care. The sum of the subarray a[j..i-1] is exactly P[i] - P[j]. That subarray sum is strictly positive precisely when P[i] - P[j] > 0, which rearranges to P[j] < P[i]. So every ascending pair of prefix sums corresponds to one subarray with a strictly positive sum, and vice versa:

number of subarrays with sum > 0
   = number of pairs (j, i), j < i, with P[j] < P[i]

Counting positive-sum subarrays naively is an O(n^2) double loop. Routing it through prefix sums turns it into the counting problem above, and that is the version a Fenwick tree dispatches in O(n log n). The same template, with the comparison swapped, counts negative-sum subarrays (P[j] > P[i]) or, with two queries, subarrays whose sum lands in a target range.

Brute Force First

I always like to pin down the answer with an obviously-correct baseline before optimizing. Here it is the double loop over prefix-sum pairs:

long long brute(const vector<long long>& P) {
    long long ans = 0;
    for (int i = 0; i < (int)P.size(); ++i)
        for (int j = 0; j < i; ++j)
            if (P[j] < P[i]) ++ans;
    return ans;
}

Correct, trivial, and quadratic. The cost is the inner scan: for every prefix sum I re-examine all earlier ones. The whole game is to answer "how many earlier values are below this one?" without that linear rescan.

The Fenwick Tree Idea

The inner question is a dynamic rank query: as I sweep the prefix sums left to right, I keep a growing multiset of the values I have already seen, and at each new value I ask how many of them are strictly smaller. A Fenwick tree over the value domain answers exactly that. I treat the BIT as a frequency table indexed by value: position v stores how many times the value v has appeared so far. Then:

Sweeping once and doing one query plus one update per prefix sum gives O(n log n) overall. The order matters: I query before I insert, so the current value never counts itself, and only genuinely earlier values are in the table.

// per prefix sum, in left-to-right order:
ans += bit.query(rank(P[i]) - 1);   // earlier sums strictly smaller
bit.update(rank(P[i]), +1);          // now P[i] joins the table

Coordinate Compression

One catch: a Fenwick tree is indexed by small positive integers, but prefix sums can be enormous, negative, or both. I cannot allocate an array indexed by raw sums. The fix is coordinate compression, which I covered in Patterns & Practice and lean on here. I collect all n + 1 prefix sums, sort the distinct values, and replace each prefix sum by its 1-based rank in that sorted list. Ranks live in [1, m] where m is the number of distinct prefix sums, so the BIT needs only m + 1 slots.

Compression also handles equal prefix sums cleanly. Two equal sums share a rank, so query(rank - 1) excludes them, which is what "strictly smaller" demands. If I ever wanted "smaller or equal" instead, I would query rank rather than rank - 1.

A Worked Example

Let me take a = [3, -2, 1, -4, 2]. The prefix sums are

P = [0, 3, 1, 2, -2, 0]

Sorting the distinct values {-2, 0, 1, 2, 3} gives the rank map below, so m = 5.

prefix sum−20123
rank12345

Now I sweep P left to right, querying the count strictly below and then inserting:

stepP[i]rankquery(rank−1)running total
00200
13511
21312
32424
4−2104
50215

The total is 5. As a sanity check I can enumerate the subarrays of a with a strictly positive sum: [3], [3,-2], [3,-2,1], [1], and [2]. Five of them, matching exactly. The animation below runs this very example. Each step highlights the current prefix sum, shows how many stored sums sit below it, adds that to the tally, and then folds the value into the frequency BIT along the orange update path.

Counting Smaller Prefix Sums

Prefix sums P (swept left to right)

Frequency BIT (indexed by rank 1..m)

Smaller pairs: 0

The Code

Putting compression and the sweep together, here is the whole solution. It returns the count of smaller prefix-sum pairs, which equals the number of positive-sum subarrays. I have checked it against the brute force on several hundred random arrays with mixed signs, and the two always agree.

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
    void update(int i, int delta) { for (; i <= n; i += i & (-i)) bit[i] += delta; }
    int  query(int i) { int s = 0; for (; i > 0; i -= i & (-i)) s += bit[i]; return s; }
};

long long countSmallerPrefixPairs(const vector<long long>& a) {
    int n = a.size();
    vector<long long> P(n + 1, 0);
    for (int i = 0; i < n; ++i) P[i + 1] = P[i] + a[i];

    // coordinate compress the prefix sums to ranks [1, m]
    vector<long long> sorted(P);
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    int m = sorted.size();
    auto rankOf = [&](long long x) {
        return int(lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin()) + 1;
    };

    Fenwick fw(m);
    long long ans = 0;
    for (int i = 0; i <= n; ++i) {
        int r = rankOf(P[i]);
        ans += fw.query(r - 1);   // earlier prefix sums strictly smaller
        fw.update(r, 1);          // record P[i]
    }
    return ans;
}

The structure is the same one I use for inversion counting: compress, sweep, query-then-update. Only the direction of the comparison changes. That reuse is the whole point of internalizing the pattern.

Strictly Less, At Most, and Range Variants

Small edits to the same loop unlock a family of questions. I keep these straight by remembering that the BIT answers "how many stored values lie in a prefix of the value axis," and everything else is arithmetic on prefix queries.

Other Patterns Where Fenwick Trees Shine

The prefix-sum count is one member of a large family. Every entry below is the same "sweep and ask a prefix-count question" idea wearing a different costume, and I solve all of them with the identical Fenwick skeleton.

Segment Tree: When I Reach for It Instead

It is fair to ask why I did not just use a segment tree, since a count segment tree over the compressed value axis solves this exact problem with the same asymptotics. Point-update +1 at a rank, range-query the count over [1, rank - 1], and the answer falls out in O(n log n) as well. My honest take: for this problem the Fenwick tree is the better tool, and here is the reasoning I apply.

The query I need is a prefix aggregate of a commutative group (a running count) under point updates. That is precisely the niche a Fenwick tree was designed for. It gives me roughly half the memory, a smaller constant factor, and about a dozen lines of code with no recursion, no lazy propagation, and no node arithmetic to get wrong. When the operation is "add at a point, sum over a prefix," I default to the BIT every time.

The segment tree earns its extra weight when the problem grows past a plain prefix count:

So my rule of thumb is simple. If I can phrase the query as "point update, prefix sum," the Fenwick tree wins on size, speed, and simplicity, and counting smaller prefix sums is squarely in that bucket. The day the query couples an index range with a value threshold, or asks for order statistics inside a subarray, or wants a non-invertible combine, I switch to a segment tree and accept the extra code for the extra power.

Complexity and Takeaways

Building prefix sums is O(n), sorting for compression is O(n log n), and the sweep does n + 1 Fenwick operations at O(log m) each, for O(n log n) overall and O(m) extra space. The lasting lesson I take from this problem is the reduction in both directions: a question about subarray sums becomes a question about ordered pairs of prefix sums, and a question about ordered pairs becomes a sweep with a dynamic rank query. Once a problem is in that shape, the Fenwick tree is almost always the shortest path to O(n log n).