Grade 9 · Frequency arrays, prefix sums and the Sieve of EratosthenesCitește în română

Marking ranges with a difference array

Original: Marcarea intervalelor cu vectorul de diferențe

O(n)C++1745 lines1 example

The idea

We have n positions, initially 0, and m operations 'add 1 to positions a..b'. Instead of walking every range, we only note its ends: d[a]++ (it starts here) and d[b + 1]-- (it ends here). At the end, the prefix sums of d give the value of every position. n and m are read, then m pairs a b; the n values are printed.

Original description (Romanian)

Avem n poziții, inițial 0, și m operații „adună 1 pe pozițiile a..b”. În loc să parcurgem fiecare interval, notăm doar capetele: d[a]++ (de aici începe) și d[b + 1]-- (aici se termină). La final, sumele parțiale ale lui d dau valoarea fiecărei poziții. Se citesc n și m, apoi m perechi a b; se afișează cele n valori.

Complexity: O(n + m), compared with O(n · m) with direct marking
Grade: Grade 9 (Clasa a IX-a)
Chapter: Frequency arrays, prefix sums and the Sieve of Eratosthenes

Examples

Example 1

Input

Expected output

1 2 2 1 2 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

vector-de-diferente.cpp

/*
 * Titlu: Marcarea intervalelor cu vectorul de diferențe
 * Clasa: 9
 * Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
 * Descriere: Avem n poziții, inițial 0, și m operații „adună 1 pe pozițiile
 *            a..b”. În loc să parcurgem fiecare interval, notăm doar capetele:
 *            d[a]++ (de aici începe) și d[b + 1]-- (aici se termină). La final,
 *            sumele parțiale ale lui d dau valoarea fiecărei poziții.
 *            Se citesc n și m, apoi m perechi a b; se afișează cele n valori.
 * Complexitate: O(n + m), față de O(n · m) cu marcarea directă
 *
 * Exemplu
 * Intrare:
 * 6 3
 * 1 3
 * 2 5
 * 5 6
 * Ieșire: 1 2 2 1 2 1
 */
#include <iostream>
using namespace std;

int d[100002];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int a, b;
        cin >> a >> b;
        d[a]++;
        d[b + 1]--;
    }
    int valoare = 0;
    for (int i = 1; i <= n; i++)
    {
        valoare = valoare + d[i];
        cout << valoare << ' ';
    }
    cout << '\n';
    return 0;
}

Input (stdin)

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.