Lucky prefixes

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

#define rep(i, a, b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 5;

struct segment_tree {
    long long mn[4 * N];
    long long lz[4 * N];

    segment_tree() {
        memset(mn, 0, sizeof(mn));
        memset(lz, 0, sizeof(lz));
    }

    void push(int id) {
        mn[id << 1] += lz[id];
        lz[id << 1] += lz[id];
        mn[id << 1 | 1] += lz[id];
        lz[id << 1 | 1] += lz[id];
        lz[id] = 0;
    }

    void upd(int id, int tl, int tr, int l, int r, long long x) {
        if (l <= tl && tr <= r) {
            mn[id] += x;
            lz[id] += x;
            return;
        }
        if (lz[id] != 0) {
            push(id);
        }
        int tm = (tl + tr) >> 1;
        if (r <= tm) {
            upd(id << 1, tl, tm, l, r, x);
        } else if (tm + 1 <= l) {
            upd(id << 1 | 1, tm + 1, tr, l, r, x);
        } else {
            upd(id << 1, tl, tm, l, r, x);
            upd(id << 1 | 1, tm + 1, tr, l, r, x);
        }
        mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
    }

    long long get(int id, int tl, int tr, int l, int r) {
        if (l <= tl && tr <= r) {
            return mn[id];
        }
        if (lz[id] != 0) {
            push(id);
        }
        int tm = (tl + tr) >> 1;
        if (r <= tm) {
            return get(id << 1, tl, tm, l, r);
        } else if (tm + 1 <= l) {
            return get(id << 1 | 1, tm + 1, tr, l, r);
        } else {
            return min(get(id << 1, tl, tm, l, r), get(id << 1 | 1, tm + 1, tr, l, r));
        }
    }
};

int n, q;
int a[N];
segment_tree st;

void upd(int id, int x) {
    long long d = x - a[id];
    a[id] = x;
    st.upd(1, 1, n, id, n, d);
}

string que(int l, int r) {
    return st.get(1, 1, n, l, r) >= (l == 1 ? 0 : st.get(1, 1, n, l - 1, l - 1)) ? "YES" : "NO";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> q;
    long long z = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        z += a[i];
        st.upd(1, 1, n, i, i, z);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i, x;
            cin >> i >> x;
            upd(i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << que(l, r) << '\n';
        }
    }
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED