How to Efficiently Update Array Sums After Each Modification (O(N+Q) Solution)

Problem Description

Given an array of n positive integers and q operations. Each operation provides a 1‑based index i and a new value x; replace the element at position i with x and output the sum of all array elements after the change.

Input

First line: two integers n and q. Second line: n integers a_i. Next q lines: each contains i and x.

Output

For each operation output a single integer – the current sum of the array after applying that operation.

Example

Input

5 3
1 2 3 4 5
2 3
3 3
5 1

Output

16
16
12

Explanation

After the first update the array becomes [1,3,3,4,5] (sum 16). The second update does not change the array (sum 16). After the third update the array becomes [1,3,3,4,1] (sum 12).

Solution Idea

Maintain a variable sum equal to the current total. For each operation:

sum -= a[i];
sum += x;
a[i] = x;

Convert the 1‑based index to 0‑based with i -= 1 before accessing the array. Store each resulting sum and print them in order.

Reference Implementations

Python

n, q = map(int, input().split())
a = list(map(int, input().split()))
total = sum(a)
answers = []
for _ in range(q):
    i, x = map(int, input().split())
    i -= 1
    total -= a[i]
    total += x
    a[i] = x
    answers.append(total)
for v in answers:
    print(v)

Java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        long sum = 0;
        for (int v : a) sum += v;
        int[] out = new int[q];
        for (int k = 0; k < q; k++) {
            int i = sc.nextInt() - 1;
            int x = sc.nextInt();
            sum -= a[i];
            sum += x;
            a[i] = x;
            out[k] = (int) sum;
        }
        for (int v : out) System.out.println(v);
    }
}

C++

#include <iostream>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    int a[100000]; // adjust size as needed
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long sum = 0;
    for (int i = 0; i < n; ++i) sum += a[i];
    for (int k = 0; k < q; ++k) {
        int i, x;
        cin >> i >> x;
        --i;
        sum -= a[i];
        sum += x;
        a[i] = x;
        cout << sum << endl;
    }
    return 0;
}

Complexity Analysis

Time complexity: O(n + q) – one pass to compute the initial sum and constant time per update. Space complexity: O(1) extra beyond the input array and output list.