Cses range update range sums hard

#include <iostream>   // For cin, cout
#include <cassert>
#include <vector>     // For vector container
#include <tuple>      // For tuple
#include <random>     // For mt19937 and uniform_int_distribution
#include <chrono>     // For timing
#include <algorithm>  // For swap
#include <cstdint>    // For int64_t if needed

using namespace std;
using namespace chrono;

// ===================== Configuration =====================
#define VALUE uint64_t
#define MAXN 200001
#define LSB(x)           ((x) & -(x))
#define PARENT(x)        ((x) + LSB(x))
#define LEFT_SIBLING(x)  ((x) - LSB(x))

const int LOGN = 18;

// ===================== Global Arrays =====================
VALUE point[MAXN];
VALUE tree[MAXN];

int lazy_set[MAXN];
VALUE lazy_increase[MAXN];
int n_fenwick;

// ===================== Macros for Combine =====================
#define combine_value(a, b) ((a) + (b))
#define DEFAULT_COMBINE (0ll)

const int INCREASE = 1;
const int SET = 2;

// ===================== Core Functions =====================
bool update_point(int nd, VALUE value, int type) {
    if (type == SET) {
        int64_t delta = value - point[nd];
        point[nd] = value;
        tree[nd] += delta;
        return false;
    } else {
        tree[nd] += value;
        point[nd] += value;
        return false;
    }
}

void update_interval(int nd, VALUE value, int type) {
    if (type == SET) {
        lazy_set[nd] = value;
        lazy_increase[nd] = 0;
    } else {
        lazy_increase[nd] += value;
    }

    if (type == SET) {
        tree[nd] = value * LSB(nd);
        point[nd] = value;
    } else {
        tree[nd] += value * LSB(nd);
        point[nd] += value;
    }
}

#define foreach_fenwick_children(child, nd) \
    for (int sibling = LEFT_SIBLING(nd), child = (nd) - 1; child > sibling; child -= LSB(child))

void push_lazy(int nd) {
    if (nd > n_fenwick) return;
    if (!lazy_set[nd] && !lazy_increase[nd]) return;

    foreach_fenwick_children(child, nd) {
        if (lazy_set[nd]) {
            update_interval(child, lazy_set[nd], SET);
        }
        if (lazy_increase[nd]) {
            update_interval(child, lazy_increase[nd], INCREASE);
        }
    }

    lazy_set[nd] = lazy_increase[nd] = 0;
}

int go_up(int lo, int hi, int* record) {
    int cnt = 0;
    while (lo < hi) {
        record[cnt++] = lo;
        lo = PARENT(lo);
    }
    return cnt;
}

void pull_lazy(int lo, int hi) {
    static int parent[LOGN];
    int cnt = go_up(PARENT(lo), hi, parent);
    while (cnt--) {
        push_lazy(parent[cnt]);
    }
}

void combine(int nd) {
    if (nd > n_fenwick) return;
    tree[nd] = point[nd];
    foreach_fenwick_children(chld, nd) {
        tree[nd] = combine_value(tree[chld], tree[nd]);
    }
}

void recalculate(int lo, int hi) {
    while (lo < hi) {
        combine(lo);
        lo = PARENT(lo);
    }
}

#define fenwick_range_iter(l, r, i, i_point) for (int i = (r), next_r, i_point;(l) <= i && (next_r = LEFT_SIBLING(i), (i_point = (next_r < (l) - 1)), true);i = (i_point ? i - 1 : next_r))

// ===================== Update / Query =====================
void range_update_fenwick(int l, int r, int v, int type) {
    int previous_node = 0;
    int first_point = 0;
    bool node_dirty = false;

    pull_lazy(r, n_fenwick + 1);

    fenwick_range_iter(l, r, i, i_point) {
        if (i_point) {
            node_dirty = update_point(i, v, type);
            if (first_point == 0) first_point = i;
            if (l != i || node_dirty) push_lazy(i);
        } else {
            update_interval(i, v, type);
            node_dirty = false;
        }

        previous_node = i;
    }

    recalculate(PARENT(r), PARENT(first_point ? first_point : previous_node));
    recalculate(node_dirty ? previous_node : PARENT(previous_node),
                n_fenwick + 1);
}

VALUE range_query_fenwick(int l, int r) {
    assert(l <= r);
    VALUE ans;
    bool empty = true;

    pull_lazy(r, n_fenwick + 1);

    fenwick_range_iter(l, r, i, i_point) {
        const VALUE& segment = i_point ? point[i] : tree[i];
        ans = empty ? segment : combine_value(segment, ans);
        empty = false;

        if (i_point && l != i) {
            push_lazy(i);
        }
    }
    return ans;
}

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

    int n, q;
    cin >> n >> q;
    n_fenwick = n;

    for (int i = 1; i <= n; ++i) {
        tree[i] = DEFAULT_COMBINE;
        lazy_set[i] = 0;
        lazy_increase[i] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        VALUE v;
        cin >> v;
        point[i] = v;
        tree[i] = combine_value(tree[i], point[i]);
        int parent = PARENT(i);
        if (parent <= n) {
            tree[parent] = combine_value(tree[parent], tree[i]);
        }
    }

    while (q--) {
        int t, a, b, x;
        cin >> t >> a >> b;

        if (t == 3) { // Query
            cout << range_query_fenwick(a, b) << endl;
        } else { // Update
            cin >> x;
            range_update_fenwick(a, b, x, t == 1 ? INCREASE : SET);
        }
    }

    return 0;
}