Arrays and Vectors

An array stores a sequence of elements of one type in consecutive memory locations. An index names a position, so a program can reach the fifth value directly instead of walking through the first four. A vector is a standard-library dynamic array: it offers the same direct indexing while allowing its length to change. These are the basic storage tools behind adjacency lists, DP tables, frequency arrays, sorting, and almost every later data structure. This lesson builds a small sequence processor, then uses prefix sums to answer interval-sum questions. Understanding which operations move elements matters more than memorizing container names.

Prerequisites: Variables, for loops, functions, and basic arithmetic.

Build the idea

1. Separate positions from values. For the sequence [4, -1, 7, 2], position 3 contains 7. C++ containers are physically indexed from 0, but vector<long long> a(n + 1) lets us deliberately use positions 1 through n and leave position 0 unused. There are n useful elements, not n+1. Accessing a[i] takes O(1) because the address follows from the starting address, element size, and index. Access outside the allocated range is undefined behavior; it is not a reliable way to obtain a zero.
2. Choose fixed or changing length. A built-in array such as int a[1000]{}; has a fixed compile-time capacity and zero-initializes its elements. std::array<int, 1000> wraps fixed-size storage with standard container operations. A vector can be sized from input. vector<int> v(n) creates n actual elements; v.reserve(n) only requests storage and leaves its length unchanged. After reserve, writing v[0] is invalid if the vector is still empty. Use push_back to append or resize to create indexed positions.
3. Understand growth rather than fearing it. A vector tracks size, the number of existing elements, and capacity, the allocated room. Most appends only construct the next element. An append that exhausts capacity allocates a larger block and moves or copies old elements. Thus one push_back can take linear time, while a sequence of appends has amortized constant cost per append. Reallocation invalidates pointers, references, and iterators to elements. Inserting or erasing in the middle shifts the suffix and costs O(n), even if capacity is sufficient. Repeatedly erasing the first element of a vector is therefore a poor queue implementation.
4. Build a prefix invariant. Define pref[0] = 0 and pref[i] = pref[i-1] + a[i]. After processing i, pref[i] equals the sum of positions 1 through i. For [4, -1, 7, 2], the prefix array is [0, 4, 3, 10, 12]. A query [2,4] is pref[4] - pref[1] = 8: subtraction removes exactly positions before 2. The extra zero position makes intervals beginning at 1 obey the same formula. This is preprocessing, not a dynamic update structure; changing a[2] invalidates every later prefix sum.
5. Read the implementation. a owns the input values; pref owns cumulative sums; l and r are inclusive endpoints. The first output line prints the stored sequence in reverse using indexing, without modifying it. Each following line answers one interval query. Ordinary int values are converted into long long sums so several large values do not overflow 32 bits. Bounds are validated before allocation or indexing. Prefix sums still require that the total fit in long long. In a contest, state that numeric assumption explicitly instead of assuming a wider type can never overflow.
6. When the operation changes, change the tool. Direct indexing and appending suggest vector. Frequent insertion at known linked positions suggests a list; removing at both ends suggests deque. Static interval sums suggest prefix sums. Point changes with later sum queries suggest Fenwick or segment trees. For a two-dimensional DP table, a vector of vectors is convenient but each inner vector has separate storage; it is not one contiguous rectangle. Adjacency lists use exactly that structure because different vertices have different numbers of neighbors.

C++17 implementation

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    if(!(cin>>n>>q)||n<0||q<0){
        return 0;
    }
    // Construct n+1 elements; position 0 is unused input and the zero prefix.
    vector<long long>a(n+1),pref(n+1,0);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i]; // Sum of the first i values.
    }
    // Read in reverse index order without moving the stored elements.
    for(int i=n;i>=1;--i){
        if(i!=n){
            cout<<' ';
        }
        cout<<a[i];
    }
    cout<<'\n';
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l<1||r>n||l>r){
            cout<<"INVALID\n";
        }
        else{
            // Subtract the prefix before l, leaving exactly positions l..r.
            cout<<pref[r]-pref[l-1]<<'\n';
        }
    }
}

Complexity analysis

Indexing is O(1). Vector construction and prefix preprocessing are O(n), reverse printing is O(n), and each sum query is O(1), giving O(n+q) total time and O(n) storage. push_back is amortized O(1), but one growth can be O(n); middle insertion/deletion is O(n). These bounds describe different operations and should not be merged into a claim that every vector operation is constant time.

Common mistakes and edge cases. Do not confuse reserve with resize, write index n into a vector of length n, or access front/back on an empty vector. A loop with unsigned size_t can wrap below zero when counting backward; the code uses a signed int index. Never keep a reference across a possible reallocation. Prefix sums do not support updates without rebuilding. Large local fixed arrays can exhaust the stack; vector storage usually avoids that problem.

Example input and output

First n and q (n,q ≥ 0), then n signed values, then q inclusive intervals l r with 1 ≤ l ≤ r ≤ n. All sums must fit in signed 64 bits. For n=0 only q=0 is meaningful; the program prints an empty first line.

Input

Output

The first line reverses the stored values. The three interval sums are -1+7+2=8, 4, and 4-1+7+2=12. A single-element interval uses the same formula as a longer interval.

Practical applications

Use vectors for input sequences, DP states, adjacency lists, and compact indexed tables. Prefix sums support static range sums and counting intervals; difference arrays are a related technique for offline range additions. Learn Fenwick and segment trees when queries are interleaved with modifications.

Check your understanding

After vector<int> v; v.reserve(10); how many elements may be indexed?

Put it into practice

Extend the program to answer how many even values occur in each interval, without scanning the interval.

Show a hint

Build a second prefix array containing 1 for an even element and 0 otherwise.

Next lesson →