// Build Segment Tree — O(N)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int tree[4 * MAXN];  // Segment tree array (4x array length)
int arr[MAXN];       // Original array

// Build: recursively fill tree[]
// node = current tree node index (1-indexed)
// start, end = range covered by this node
void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node: store array element
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // Build left and right children first
        build(2 * node, start, mid);        // Left child
        build(2 * node + 1, mid + 1, end);  // Right child
        // Internal node: sum of children
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1);  // Build from node 1, covering [0..n-1]

    return 0;
}

build(1, 0, 5):
  build(2, 0, 2):
    build(4, 0, 1):
      build(8, 0, 0): tree[8] = arr[0] = 1
      build(9, 1, 1): tree[9] = arr[1] = 3
      tree[4] = tree[8] + tree[9] = 4
    build(5, 2, 2): tree[5] = arr[2] = 5
    tree[2] = tree[4] + tree[5] = 9
  build(3, 3, 5):
    ...
    tree[3] = 27
  tree[1] = 9 + 27 = 36

// Range Query: sum of arr[l..r] — O(log N)
// node = current tree node, [start, end] = covered range
// [l, r] = query range
int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        // Case 1: current interval completely outside query range
        return 0;   // Identity element for sum (use INT_MAX for min)
    }
    if (l <= start && end <= r) {
        // Case 2: current interval completely inside query range
        return tree[node];   // ← Key line: use this node directly!
    }
    // Case 3: partial overlap — recurse into children
    int mid = (start + end) / 2;
    int leftSum  = query(2 * node, start, mid, l, r);
    int rightSum = query(2 * node + 1, mid + 1, end, l, r);
    return leftSum + rightSum;
}

// Usage: sum of arr[2..4]
int result = query(1, 0, n - 1, 2, 4);
cout << result << "\n";  // 5 + 7 + 9 = 21

// Point Update: set arr[idx] = val — O(log N)
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Leaf node: update value
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);      // Update in left subtree
        } else {
            update(2 * node + 1, mid + 1, end, idx, val); // Update in right subtree
        }
        // After child changes, update this internal node
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

// Usage: set arr[2] = 10
update(1, 0, n - 1, 2, 10);

// Segment Tree — O(N) build, O(log N) query/update
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long tree[4 * MAXN];

void build(int node, int start, int end, long long arr[]) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid, arr);
    build(2 * node + 1, mid + 1, end, arr);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

long long query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r)
         + query(2 * node + 1, mid + 1, end, l, r);
}

void update(int node, int start, int end, int idx, long long val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    long long arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1, arr);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: set arr[i] = v
            int i; long long v;
            cin >> i >> v;
            update(1, 0, n - 1, i, v);
        } else {
            // Range query: sum of arr[l..r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

// Range Minimum Segment Tree — same structure, different operation
void build_min(int node, int start, int end, int arr[]) {
    if (start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build_min(2*node, start, mid, arr);
    build_min(2*node+1, mid+1, end, arr);
    tree[node] = min(tree[2*node], tree[2*node+1]);  // ← Changed to min
}

int query_min(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return INT_MAX;   // ← Identity element for min
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return min(query_min(2*node, start, mid, l, r),
               query_min(2*node+1, mid+1, end, l, r));
}

// Segment Tree with Lazy Propagation
// Supports: range add update, range sum query — each O(log N)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

ll tree[4 * MAXN];   // tree[node] = range sum
ll lazy[4 * MAXN];   // lazy[node] = pending add value (0 = no pending)

// ── Push Down: pass pending lazy to children ──
void pushDown(int node, int start, int end) {
    if (lazy[node] == 0) return;  // No pending update

    int mid = (start + end) / 2;
    int left = 2 * node, right = 2 * node + 1;

    // Update left child's sum: add lazy * (number of elements in left child)
    tree[left]  += lazy[node] * (mid - start + 1);
    tree[right] += lazy[node] * (end - mid);

    // Pass lazy to children
    lazy[left]  += lazy[node];
    lazy[right] += lazy[node];

    // Clear current node's lazy (already pushed down)
    lazy[node] = 0;
}

// ── Build ──
void build(int node, int start, int end, ll arr[]) {
    lazy[node] = 0;
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2*node, start, mid, arr);
    build(2*node+1, mid+1, end, arr);
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── Range Update: add val to all elements in [l, r] ──
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;  // Out of range: no-op

    if (l <= start && end <= r) {
        // Current interval completely inside [l, r]: apply lazy, don't recurse
        tree[node] += val * (end - start + 1);  // ← Key: multiply by interval length
        lazy[node] += val;                        // Store pending value for children
        return;
    }

    // Partial overlap: push down existing lazy first, then recurse
    pushDown(node, start, end);  // ← Key: must pushDown before recursing!

    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);

    // Update current node from children
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── Range Query: sum of elements in [l, r] ──
ll query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;  // Out of range

    if (l <= start && end <= r) {
        return tree[node];  // Completely inside: return stored sum (already includes lazy!)
    }

    // Partial overlap: push down first, then recurse
    pushDown(node, start, end);  // ← Key: must pushDown before recursing!

    int mid = (start + end) / 2;
    ll leftSum  = query(2*node,   start, mid, l, r);
    ll rightSum = query(2*node+1, mid+1, end, l, r);
    return leftSum + rightSum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    ll arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n-1, arr);

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            // Range update: add val to [l, r]
            int l, r; ll val;
            cin >> l >> r >> val;
            update(1, 0, n-1, l, r, val);
        } else {
            // Range query: sum of [l, r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n-1, l, r) << "\n";
        }
    }

    return 0;
}

// Segment Tree with Range Assignment Lazy
// tree[i] = range sum, lazy[i] = assign marker (-1 = no marker)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;

ll tree[4*MAXN];
ll lazy[4*MAXN];  // -1 = no marker

void build(int s, int t, int p, ll a[]) {
    lazy[p] = -1;
    if (s == t) { tree[p] = a[s]; return; }
    int m = s + ((t - s) >> 1);
    build(s, m, p*2, a);
    build(m+1, t, p*2+1, a);
    tree[p] = tree[p*2] + tree[p*2+1];
}

// ── pushDown: range assignment ──
void pushDown(int p, int s, int t) {
    if (lazy[p] == -1) return;
    int m = s + ((t - s) >> 1);
    // Assign lazy[p] to all elements in left child, count = m-s+1
    tree[p*2]   = lazy[p] * (m - s + 1);
    tree[p*2+1] = lazy[p] * (t - m);
    lazy[p*2]   = lazy[p];   // Overwrite (not accumulate!)
    lazy[p*2+1] = lazy[p];
    lazy[p] = -1;             // Clear marker
}

// ── Range assignment update ──
void update(int l, int r, ll c, int s, int t, int p) {
    if (l <= s && t <= r) {
        tree[p] = c * (t - s + 1);  // Assign entire segment
        lazy[p] = c;
        return;
    }
    pushDown(p, s, t);
    int m = s + ((t - s) >> 1);
    if (l <= m) update(l, r, c, s, m, p*2);
    if (r > m)  update(l, r, c, m+1, t, p*2+1);
    tree[p] = tree[p*2] + tree[p*2+1];
}

// ── Range sum query (same as range add version, pushDown first) ──
ll query(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return tree[p];
    pushDown(p, s, t);
    int m = s + ((t - s) >> 1);
    ll res = 0;
    if (l <= m) res += query(l, r, s, m, p*2);
    if (r > m)  res += query(l, r, m+1, t, p*2+1);
    return res;
}

// Dynamic Node Allocation Segment Tree (Weight/Value Segment Tree)
// Typical use: range counting, K-th smallest
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;  // Node pool limit (M * log V)

int ls[MAXN], rs[MAXN];     // Left/right child indices
long long sum[MAXN];
int cnt, root;              // Node counter, root index

// Add 1 at position x (for inserting value x into weight segment tree)
void update(int &p, int s, int t, int x) {
    if (!p) p = ++cnt;          // Dynamically create node if it doesn't exist
    sum[p]++;
    if (s == t) return;
    int m = s + ((t - s) >> 1);
    if (x <= m) update(ls[p], s, m, x);
    else        update(rs[p], m+1, t, x);
}

// Range sum query
long long query(int p, int s, int t, int l, int r) {
    if (!p) return 0;           // Node doesn't exist, no elements in this range
    if (l <= s && t <= r) return sum[p];
    int m = s + ((t - s) >> 1);
    long long res = 0;
    if (l <= m) res += query(ls[p], s, m, l, r);
    if (r > m)  res += query(rs[p], m+1, t, l, r);
    return res;
}

// Usage example: insert values then query count in [l, r]
// update(root, 1, 1e9, val);
// query(root, 1, 1e9, l, r);

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long tree[4*MAXN];
int n, q;

void build(int node, int s, int e, int arr[]) {
    if (s==e) { tree[node]=arr[s]; return; }
    int mid=(s+e)/2;
    build(2*node,s,mid,arr); build(2*node+1,mid+1,e,arr);
    tree[node]=tree[2*node]+tree[2*node+1];
}
void update(int node,int s,int e,int idx,long long val) {
    if (s==e) { tree[node]=val; return; }
    int mid=(s+e)/2;
    if (idx<=mid) update(2*node,s,mid,idx,val);
    else update(2*node+1,mid+1,e,idx,val);
    tree[node]=tree[2*node]+tree[2*node+1];
}
long long query(int node,int s,int e,int l,int r) {
    if (r<s||e<l) return 0;
    if (l<=s&&e<=r) return tree[node];
    int mid=(s+e)/2;
    return query(2*node,s,mid,l,r)+query(2*node+1,mid+1,e,l,r);
}
int arr[MAXN];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n,arr);
    while(q--) {
        int t; cin>>t;
        if(t==1) { int i; long long v; cin>>i>>v; update(1,1,n,i,v); }
        else { int l,r; cin>>l>>r; cout<<query(1,1,n,l,r)<<"\n"; }
    }
}

Complexity: O(N) build, O(log N) per query/update.

Modify two lines in the above solution:

// In build/update:
tree[node] = min(tree[2*node], tree[2*node+1]);
// In query — identity element for out-of-range:
if (r < s || e < l) return INT_MAX;
// Merge:
return min(query(2*node,s,mid,l,r), query(2*node+1,mid+1,e,l,r));

Initialization: tree[leaf] = arr[s] (same). The only change is the aggregate function and identity element.

Core Idea: Coordinate compress values to [1..N]. For each element x (left to right), inversions += (number of inserted elements) - (number of inserted elements ≤ x) = query(N) - query(x). Then insert x.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int tree[MAXN], n;
void update(int i){for(;i<=n;i+=i&-i) tree[i]++;}
int query(int i){int s=0;for(;i>0;i-=i&-i)s+=tree[i];return s;}

int main(){
    cin>>n;
    vector<int> a(n);
    for(int&x:a)cin>>x;
    // Coordinate compression
    vector<int> sorted=a; sort(sorted.begin(),sorted.end());
    sorted.erase(unique(sorted.begin(),sorted.end()),sorted.end());
    for(int&x:a) x=lower_bound(sorted.begin(),sorted.end(),x)-sorted.begin()+1;
    int m=sorted.size();

    long long inv=0;
    for(int i=0;i<n;i++){
        inv += (i - query(a[i]));  // Count of already-seen elements greater than a[i]
        update(a[i]);
    }
    cout<<inv<<"\n";
}

Complexity: O(N log N), using BIT (more appropriate than Segment Tree for this problem).