Binary Indexed Tree (Fenwick)

// BIT (Fenwick Tree) — Generic Template
// time = O(log N) per update/query, space = O(N)
class BIT {
    int[] tree;
    int n;
    BIT(int n) { this.n = n; tree = new int[n + 1]; }
    void update(int i, int delta) {          // 1-indexed; add delta at position i
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    int query(int i) {                        // prefix sum [1..i]
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    int query(int l, int r) { return query(r) - query(l - 1); } // range [l..r]
}

n = 8, tree[i] covers the range (i - lowbit(i), i]   (1-indexed)

 i  | binary | lowbit | tree[i] covers
----+--------+--------+----------------
 1  |  0001  |   1    | [1..1]
 2  |  0010  |   2    | [1..2]
 3  |  0011  |   1    | [3..3]
 4  |  0100  |   4    | [1..4]
 5  |  0101  |   1    | [5..5]
 6  |  0110  |   2    | [5..6]
 7  |  0111  |   1    | [7..7]
 8  |  1000  |   8    | [1..8]

QUERY prefix(7): walk DOWN, i -= lowbit(i)   -> ADD disjoint blocks
    7 -> 6 -> 4 -> 0
    tree[7]  + tree[6]  + tree[4]
    [7..7]   + [5..6]   + [1..4]      = [1..7]   (exactly covers, no overlap)

UPDATE at 3: walk UP, i += lowbit(i)         -> every block CONTAINING 3
    3 -> 4 -> 8
    tree[3], tree[4], tree[8]
    [3..3]  [1..4]   [1..8]

Both walks strip / carry one bit per step  =>  O(log N).

// LC 1505 - Minimum Possible Integer After at Most K Adjacent Swaps On Digits
// IDEA: greedy smallest digit + BIT over POSITIONS to get the real (post-removal) swap cost
// time = O(N * 10 * log N), space = O(N)
public String minInteger(String num, int k) {
    int n = num.length();
    // queue of original indices for each digit, ascending
    List<Deque<Integer>> pos = new ArrayList<>();
    for (int d = 0; d <= 9; d++) pos.add(new ArrayDeque<>());
    for (int i = 0; i < n; i++) pos.get(num.charAt(i) - '0').addLast(i);

    BIT removed = new BIT(n);          // 1 at index -> that digit is already consumed
    StringBuilder sb = new StringBuilder();

    for (int step = 0; step < n; step++) {
        for (int d = 0; d <= 9; d++) {
            if (pos.get(d).isEmpty()) continue;
            int i = pos.get(d).peekFirst();               // earliest remaining occurrence
            // removed.query(i) = consumed digits among original idx 0..i-1
            int cost = i - removed.query(i);              // swaps needed to bring it to the front
            if (cost <= k) {
                k -= cost;
                pos.get(d).pollFirst();
                removed.update(i + 1, 1);                 // +1 -> 1-indexed BIT
                sb.append((char) ('0' + d));
                break;
            }
        }
    }
    return sb.toString();
}

# python
# LC 1505 - Minimum Possible Integer After at Most K Adjacent Swaps On Digits
# IDEA: greedy smallest digit + BIT over POSITIONS to get the real (post-removal) swap cost
# time = O(N * 10 * log N), space = O(N)
# (reuses the BIT class from 2-13)
from collections import deque


def minInteger(num, k):
    n = len(num)
    pos = [deque() for _ in range(10)]          # original indices per digit
    for i, ch in enumerate(num):
        pos[int(ch)].append(i)

    removed = BIT(n)                            # 1 at index -> digit already consumed
    out = []

    for _ in range(n):
        for d in range(10):
            if not pos[d]:
                continue
            i = pos[d][0]                       # earliest remaining occurrence
            cost = i - removed.query(i)         # consumed among original idx 0..i-1
            if cost <= k:
                k -= cost
                pos[d].popleft()
                removed.update(i + 1, 1)        # +1 -> 1-indexed BIT
                out.append(str(d))
                break
    return "".join(out)

// LC 1409 - Queries on a Permutation With Key
// IDEA: BIT over POSITIONS — n spare front slots; query(p-1) = # alive before p = current index
// time = O(N log(N+M)), space = O(N + M)
public int[] processQueries(int[] queries, int m) {
    int n = queries.length, size = n + m;
    BIT bit = new BIT(size);
    int[] posOf = new int[m + 1];
    // value v initially lives at BIT slot n+v  (slots 1..n are the reserved front buffer)
    for (int v = 1; v <= m; v++) { posOf[v] = n + v; bit.update(n + v, 1); }

    int front = n;                       // next free slot, filled right-to-left
    int[] res = new int[n];
    for (int q = 0; q < n; q++) {
        int p = posOf[queries[q]];
        res[q] = bit.query(p - 1);       // # of alive slots before p == current 0-based index
        bit.update(p, -1);               // vacate old slot
        posOf[queries[q]] = front;
        bit.update(front, 1);            // occupy new front slot
        front--;
    }
    return res;
}

# python
# LC 1409 - Queries on a Permutation With Key
# IDEA: BIT over POSITIONS — n spare front slots; query(p-1) = # alive before p = current index
# time = O(N log(N+M)), space = O(N + M)
def processQueries(queries, m):
    n = len(queries)
    bit = BIT(n + m)
    pos_of = [0] * (m + 1)
    # value v initially lives at BIT slot n+v (slots 1..n are the reserved front buffer)
    for v in range(1, m + 1):
        pos_of[v] = n + v
        bit.update(n + v, 1)

    front = n                            # next free slot, filled right-to-left
    res = []
    for q in queries:
        p = pos_of[q]
        res.append(bit.query(p - 1))     # alive slots before p == current 0-based index
        bit.update(p, -1)                # vacate old slot
        pos_of[q] = front
        bit.update(front, 1)             # occupy new front slot
        front -= 1
    return res

// LC 307 - Range Sum Query Mutable (BIT version)
// IDEA: BIT — O(log N) point update and prefix sum; range via subtraction
// time = O(log N) per update/query, space = O(N)
class NumArray {
    int[] bit, nums;
    int n;
    public NumArray(int[] nums) {
        n = nums.length;
        this.nums = new int[n];
        bit = new int[n + 1];
        for (int i = 0; i < n; i++) update(i, nums[i]);
    }
    public void update(int i, int val) {
        int delta = val - nums[i];
        nums[i] = val;
        for (int x = i + 1; x <= n; x += x & -x) bit[x] += delta;
    }
    public int sumRange(int l, int r) { return prefix(r+1) - prefix(l); }
    private int prefix(int i) { int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
}

// LC 307 - Range Sum Query - Mutable
// IDEA: Binary Indexed Tree (Fenwick Tree)
// time = O(log N) per update/query, space = O(N)
class NumArray {
    int[] bit, nums;
    int n;
    public NumArray(int[] nums) {
        this.n = nums.length;
        this.nums = new int[n];
        this.bit = new int[n + 1];
        for (int i = 0; i < n; i++) update(i, nums[i]);
    }
    public void update(int i, int val) {
        int delta = val - nums[i];
        nums[i] = val;
        for (int x = i + 1; x <= n; x += x & (-x)) bit[x] += delta;
    }
    public int sumRange(int left, int right) {
        return prefixSum(right + 1) - prefixSum(left);
    }
    private int prefixSum(int i) {
        int sum = 0;
        for (int x = i; x > 0; x -= x & (-x)) sum += bit[x];
        return sum;
    }
}

To get sum of rectangle (r1,c1) to (r2,c2):

  query(r2, c2)           = entire top-left block
- query(r1-1, c2)         = remove rows above
- query(r2, c1-1)         = remove cols to the left
+ query(r1-1, c1-1)       = add back double-subtracted corner

Visual:

  ┌──────────┬──────────┐
  │  +added  │  -removed│     query(r1-1, c2) removes this top strip
  │  back    │  (top)   │
  ├──────────┼──────────┤  r1
  │  -removed│ ★ TARGET │
  │  (left)  │  REGION  │
  └──────────┴──────────┘  r2
            c1          c2

  sum = query(r2,c2) - query(r1-1,c2) - query(r2,c1-1) + query(r1-1,c1-1)

// LC 308 - Range Sum Query 2D - Mutable
// IDEA: 2D Binary Indexed Tree (Fenwick Tree)
// time = O(log M * log N) per update/query, space = O(M * N)
class NumMatrix {
    private int[][] tree;  // 2D BIT (1-indexed)
    private int[][] nums;  // original values (for computing delta)
    private int m, n;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        m = matrix.length;
        n = matrix[0].length;
        tree = new int[m + 1][n + 1];
        nums = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                update(i, j, matrix[i][j]);
    }

    // Point update: set matrix[row][col] = val
    public void update(int row, int col, int val) {
        int delta = val - nums[row][col];
        nums[row][col] = val;
        // Propagate delta through 2D BIT (nested lowbit traversal)
        for (int i = row + 1; i <= m; i += i & -i)
            for (int j = col + 1; j <= n; j += j & -j)
                tree[i][j] += delta;
    }

    // Prefix sum query: sum of (0,0) to (row,col)
    private int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= i & -i)
            for (int j = col + 1; j > 0; j -= j & -j)
                sum += tree[i][j];
        return sum;
    }

    // Range sum: rectangle (row1,col1) to (row2,col2)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 2D inclusion-exclusion
        return query(row2, col2)
             - query(row1 - 1, col2)
             - query(row2, col1 - 1)
             + query(row1 - 1, col1 - 1);
    }
}

// Each row has its own 1D BIT
// update = O(log N), sumRegion = O(M * log N)  — slower for large M
class NumMatrix_RowBIT {
    private BIT[] trees;

    public NumMatrix_RowBIT(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        trees = new BIT[m];
        for (int i = 0; i < m; i++) {
            trees[i] = new BIT(n);
            for (int j = 0; j < n; j++)
                trees[i].update(j + 1, matrix[i][j]);
        }
    }

    public void update(int row, int col, int val) {
        int prev = trees[row].query(col + 1) - trees[row].query(col);
        trees[row].update(col + 1, val - prev);
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++)
            sum += trees[i].query(col2 + 1) - trees[i].query(col1);
        return sum;
    }
}

// LC 315 - Count of Smaller Numbers After Self
// IDEA: BIT + coordinate compression — process right to left
// time = O(N log N), space = O(N)
public List<Integer> countSmaller(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    Map<Integer, Integer> rank = new HashMap<>();
    int r = 1;
    for (int v : sorted) if (!rank.containsKey(v)) rank.put(v, r++);
    int[] bit = new int[r];
    Integer[] result = new Integer[n];
    for (int i = n - 1; i >= 0; i--) {
        int pos = rank.get(nums[i]);
        result[i] = query(bit, pos - 1);
        update(bit, pos, r - 1);
    }
    return Arrays.asList(result);
}
private void update(int[] bit, int i, int n) {
    for (; i <= n; i += i & (-i)) bit[i]++;
}
private int query(int[] bit, int i) {
    int sum = 0;
    for (; i > 0; i -= i & (-i)) sum += bit[i];
    return sum;
}

// LC 493 - Reverse Pairs
// IDEA: BIT + coordinate compression — process right to left; query then update
// time = O(N log N), space = O(N)
public int reversePairs(int[] nums) {
    int n = nums.length;
    long[] sorted = new long[2 * n];
    for (int i = 0; i < n; i++) { sorted[i] = nums[i]; sorted[n+i] = 2L * nums[i]; }
    Arrays.sort(sorted);
    Map<Long, Integer> rank = new HashMap<>();
    int r = 1;
    for (long v : sorted) if (!rank.containsKey(v)) rank.put(v, r++);
    int[] bit = new int[r];
    int count = 0;
    for (int i = n - 1; i >= 0; i--) {
        count += queryBIT(bit, rank.get((long)nums[i]) - 1);
        updateBIT(bit, rank.get(2L * nums[i]), r - 1);
    }
    return count;
}
private void updateBIT(int[] b, int i, int n) { for (; i <= n; i += i&-i) b[i]++; }
private int  queryBIT(int[] b, int i)         { int s=0; for(;i>0;i-=i&-i) s+=b[i]; return s; }

// LC 327 - Count of Range Sum (merge sort approach)
// IDEA: Merge sort — count valid pairs during the merge step
// time = O(N log N), space = O(N)
public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
    return mergeCount(prefix, 0, n + 1, lower, upper);
}
private int mergeCount(long[] arr, int l, int r, int lo, int hi) {
    if (r - l <= 1) return 0;
    int mid = (l + r) / 2;
    int count = mergeCount(arr, l, mid, lo, hi) + mergeCount(arr, mid, r, lo, hi);
    int j = mid, k = mid;
    for (int i = l; i < mid; i++) {
        while (j < r && arr[j] - arr[i] < lo) j++;
        while (k < r && arr[k] - arr[i] <= hi) k++;
        count += k - j;
    }
    long[] tmp = Arrays.copyOfRange(arr, l, r);
    Arrays.sort(tmp);
    System.arraycopy(tmp, 0, arr, l, tmp.length);
    return count;
}

// LC 775 - Global and Local Inversions
// IDEA: Global inversions == local iff no nums[i] > nums[j] for j >= i+2
// time = O(N), space = O(1)
public boolean isIdealPermutation(int[] nums) {
    // global == local iff every element is within 1 of its sorted position
    for (int i = 0; i < nums.length; i++)
        if (Math.abs(nums[i] - i) > 1) return false;
    return true;
}

// LC 1395 - Count Number of Teams
// IDEA: BIT over VALUES — for each middle soldier, count smaller/larger on the left and right
// time = O(N log M), space = O(M)   M = value range (ratings <= 1e5)
public int numTeams(int[] rating) {
    int MAX = 100000, n = rating.length;
    int[] leftSmaller = new int[n], leftLarger = new int[n];

    // pass 1: left -> right. after j insertions, j elements sit to the left of index j
    BIT left = new BIT(MAX);
    for (int j = 0; j < n; j++) {
        leftSmaller[j] = left.query(rating[j] - 1);          // count(< rating[j])
        leftLarger[j]  = j - left.query(rating[j]);          // j - count(<= rating[j])
        left.update(rating[j], 1);
    }

    // pass 2: right -> left, and combine
    BIT right = new BIT(MAX);
    long res = 0;
    for (int j = n - 1; j >= 0; j--) {
        int rightSmaller = right.query(rating[j] - 1);
        int rightLarger  = (n - 1 - j) - right.query(rating[j]);
        res += (long) leftSmaller[j] * rightLarger           // ascending  i < j < k
             + (long) leftLarger[j]  * rightSmaller;         // descending i > j > k
        right.update(rating[j], 1);
    }
    return (int) res;
}

// BIT helper (1-indexed)
class BIT {
    int[] tree; int n;
    BIT(int n) { this.n = n; tree = new int[n + 1]; }
    void update(int i, int delta) { for (; i <= n; i += i & -i) tree[i] += delta; }
    int query(int i) { int s = 0; for (; i > 0; i -= i & -i) s += tree[i]; return s; }
}

# python
# LC 1395 - Count Number of Teams
# IDEA: BIT over VALUES — for each middle soldier, count smaller/larger on the left and right
# time = O(N log M), space = O(M)   M = value range (ratings <= 1e5)
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):          # prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s


def numTeams(rating):
    MAX = 100000
    n = len(rating)
    left_smaller = [0] * n
    left_larger = [0] * n

    # pass 1: left -> right
    left = BIT(MAX)
    for j in range(n):
        left_smaller[j] = left.query(rating[j] - 1)      # count(< rating[j])
        left_larger[j] = j - left.query(rating[j])       # j - count(<= rating[j])
        left.update(rating[j], 1)

    # pass 2: right -> left, and combine
    right = BIT(MAX)
    res = 0
    for j in range(n - 1, -1, -1):
        right_smaller = right.query(rating[j] - 1)
        right_larger = (n - 1 - j) - right.query(rating[j])
        res += left_smaller[j] * right_larger + left_larger[j] * right_smaller
        right.update(rating[j], 1)
    return res

// LC 1649 - Create Sorted Array through Instructions
// IDEA: BIT on value range — count smaller and greater elements already inserted
// time = O(N log M), space = O(M)  M = max value
public int createSortedArray(int[] instructions) {
    int MOD = 1_000_000_007, n = 100001;
    int[] bit = new int[n + 1];
    long cost = 0;
    for (int i = 0; i < instructions.length; i++) {
        int x = instructions[i];
        int smaller = query(bit, x - 1);
        int larger  = i - query(bit, x);
        cost = (cost + Math.min(smaller, larger)) % MOD;
        update(bit, x, n);
    }
    return (int) cost;
}
private void update(int[] b, int i, int n) { for (; i <= n; i += i&-i) b[i]++; }
private int  query(int[] b, int i)         { int s=0; for(;i>0;i-=i&-i) s+=b[i]; return s; }

// LC 673 - Number of Longest Increasing Subsequences
// IDEA: DP — (len[i], cnt[i]) = (LIS length at i, number of such LIS)
// time = O(N^2), space = O(N)
public int findNumberOfLIS(int[] nums) {
    int n = nums.length, maxLen = 0, result = 0;
    int[] len = new int[n], cnt = new int[n];
    for (int i = 0; i < n; i++) {
        len[i] = cnt[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) { len[i] = len[j]+1; cnt[i] = cnt[j]; }
                else if (len[j] + 1 == len[i]) cnt[i] += cnt[j];
            }
        }
        if (len[i] > maxLen) { maxLen = len[i]; result = cnt[i]; }
        else if (len[i] == maxLen) result += cnt[i];
    }
    return result;
}

// LC 406 - Queue Reconstruction by Height
// IDEA: Sort height DESC (k ASC); insert at index k — taller people already positioned
// time = O(N^2), space = O(N)
public int[][] reconstructQueue(int[][] people) {
    Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
    List<int[]> res = new ArrayList<>();
    for (int[] p : people) res.add(p[1], p);
    return res.toArray(new int[res.size()][]);
}