Lucky prefixes

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

struct T {
	long sum;
	long misum;

	T operator+(T oth) {
		return {
			sum + oth.sum,
			min({0l, misum, sum + oth.misum})
		};
	}
};

const int N = 1 << 18;
T t[N * 2];

void st_add(int k, int x) {
	k += N;
	t[k].sum += x;
	t[k].misum += x;

	while (k /= 2) {
		t[k] = t[k * 2] + t[k * 2 + 1];
	}
}

bool st_query(int l, int r) {
	l += N;
	r += N;

	T ret_l {}, ret_r {};
	while (l <= r) {
		if (l % 2 == 1) ret_l = ret_l + t[l++];
		if (r % 2 == 0) ret_r = t[r--] + ret_r;
		l /= 2;
		r /= 2;
	}

	return (ret_l + ret_r).misum >= 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	vector<int> v(n);

	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		st_add(i, v[i]);
	}

	while (q--) {
		int c, a, b;
		cin >> c >> a >> b;
		if (c == 1) {
			a--;
			st_add(a, -v[a]);
			v[a] = b;
			st_add(a, v[a]);
		} else {
			a--;
			b--;
			cout << (st_query(a, b) ? "YES" : "NO") << '\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