Hacker earth Fenwick

#include <iostream>     // For cin, cout
#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 100001
#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];
VALUE lazy[MAXN];
bool has_lazy[MAXN];
int n_fenwick;

// ===================== Macros for Combine =====================

#define combine_value(a, b)(min(a, b))
#define DEFAULT_COMBINE (1ll << 63)

// ===================== Core Functions =====================
bool update_point(int nd, int v) {
    point[nd] += v;
    return true; // node is dirty
}

void update_interval(int nd, VALUE value) {
    has_lazy[nd] = 1;
    lazy[nd] += value;
    tree[nd] += value;
    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 (!has_lazy[nd]) return;

    foreach_fenwick_children(child, nd) {
        update_interval(child, lazy[nd]);
    }
    has_lazy[nd] = false;
    lazy[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 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);
            if (first_point == 0) first_point = i;
            if (l != i || node_dirty) push_lazy(i);
        } else {
            update_interval(i, v);
            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) {
    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;
}

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[i] = 0;
        has_lazy[i] = false;
    }

    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]);
        }
    }

    for (int i = 0; i < q; i++) {
        char q;
        int l, r, z;
        cin >> q >> l >> r;

        if (q == 'q') { // Query
            cout << range_query_fenwick(l, r) << endl;
        } else { // Update
            cin >> z;
            range_update_fenwick(l, r, z);
        }
    }

    return 0;
}