You may assume that \(0\) was assigned to every element in the very beginning, and maintain the delta from the last assignments. The given query can be rephrased as follows:

1. Erase all the deltas so far and let them \(0\). Record \(x\) as the last value assigned.
2. Add \(x\) to the \(i\)-th delta.
3. Find the sum of the last value assigned and the \(i\)-th delta, and print it.

The number of deltas modified by a query of the first kind does not exceed the number of queries of the second kind after the last assignment. Thus, by maintaining “the positions with non-zero deltas,” the problem can be solved in a total of \(O(N+Q)\) time.

Alternatively, if you have a segment tree that enables a range update and a point retrieve on a sequence of length \(N\), you can solve the problem in a total of about \(O(N+Q\log N)\) time (Sample code).

A sample code follows.

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    using namespace std;
    
    unsigned N;
    cin >> N;

    // manage the sequence by the delta from `base`
    vector<unsigned long> A(N);
    unsigned base{};

    for (auto &&a : A)cin >> a;
    A.emplace(begin(A));

    // the positions that the deltas might be non-zero
    // initially, it contains all of 1, ..., N
    vector<unsigned> added_index(N);
    iota(begin(added_index), end(added_index), 1U);
    
    unsigned Q;
    cin >> Q;

    for (unsigned _{}; _ < Q; ++_) {
        unsigned type;
        cin >> type;
        if (type == 1) {
            // Erase non-zero delta
            while (!empty(added_index)) {
                A[added_index.back()] = 0;
                added_index.pop_back();
            }
            cin >> base;
        } else if (type == 2) {
            // Add to the index-th delta
            unsigned index, value;
            cin >> index >> value;
            A[index] += value;
            added_index.emplace_back(index);
        } else {
            // Find the sum of `base` and the index-th delta
            unsigned index;
            cin >> index;
            cout << base + A[index] << endl;
        }
    }

    return 0;
}