my submission

The idea is to use a lazy segment tree to get the sum of ranges in log N time complexity.

int A[N];
long long t[N << 2];

The standard segment tree idea is that the sum of a vertex’s segment is equal to the sum of vertex’s children’s segments. This is made clear in a segment tree’s construction.

void build(int i, int l, int r) {
	if (l == r) {
		t[i] = A[l];
	else {
		int m = l + (r - l) / 2;
		build(i<<1, l, m);
		build(i<<1|1, m + 1, r);
		t[i] = t[i<<1] + t[i<<1|1];

However, an eager as opposed to lazy range update on a segment tree might affect many ranges, degrading the log N time complexity of operations. For example, adding 1 to every element in the array would require the entire tree to be calculated again.

You can think of a lazy update to a range as completed for that range, but pending for its sub-range. Prior to any descent into those subranges, you should propagate the changes.

For example, say I add 1 to all values in the array: I can increase the segment tree’s root sum and remember that 1 was added to all values with a lazy tag. Any reads to that exact range will just return the range’s sum. But now what if I want the sum of a range within the one I just lazily updated? Look below.

Ignore the set operation for now. Notive the new lazy add member added to each vertex.

struct node {
	ll sum;
	ll lz_add;
	node() {}
} t[N << 2];
void add(int i, int l, int r, int a, int b, ll x) {
	if (a > b) {
	else if (l == a && r == b) {
		t[i].lz_add += x;
		t[i].sum += x * (r - l + 1);
	else {
		// 1. what should be done right here?
		int m = l + (r - l) / 2;
		add(i<<1, l, m, a, min(b, m), x);
		add(i<<1|1, m + 1, r, max(a, m + 1), b, x);
		// 2. and what should be done here?
  1. Prior to any descent into those subranges, you have to propagate the changes you made and clear the lazy tag.

  2. Since you are going to update a lower range lazily as well, the segment tree invariant needs to be upholded.

item 2 is quite simple:

t[i] = t[i<<1] + t[i<<1|1];

I will leave item 1 to you. Look at my submission or the usaco guide if you are confused. USACO guide