fenwick_tree.cpp

/*
Fenwick Tree (Binary Indexed Tree)
Mathematical Foundation: Tree structure using bit manipulation
LSB(i) = i & (-i), parent[i] = i - LSB(i), next[i] = i + LSB(i)
Range sum query: O(log n), Point update: O(log n)
Space: O(n), 1-indexed for easier implementation
*/

#include <bits/stdc++.h>
using namespace std;

// Basic Fenwick Tree (Point Update, Range Query)
// Related LeetCode Problems:
// 307. Range Sum Query - Mutable
// https://leetcode.com/problems/range-sum-query-mutable/
// 315. Count of Smaller Numbers After Self
// https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// 327. Count of Range Sum
// https://leetcode.com/problems/count-of-range-sum/
// 493. Reverse Pairs
// https://leetcode.com/problems/reverse-pairs/
// 673. Number of Longest Increasing Subsequence
// https://leetcode.com/problems/number-of-longest-increasing-subsequence/
// 1395. Count Number of Teams
// https://leetcode.com/problems/count-number-of-teams/
// 1649. Create Sorted Array through Instructions
// https://leetcode.com/problems/create-sorted-array-through-instructions/
// 2179. Count Good Triplets in an Array
// https://leetcode.com/problems/count-good-triplets-in-an-array/
// 2659. Make Array Empty
// https://leetcode.com/problems/make-array-empty/
class FenwickTree {
    vector<long long> tree;
    int n;
    
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
    
    FenwickTree(vector<int>& arr) : n(arr.size()), tree(n + 1, 0) {
        for (int i = 0; i < n; i++)
            update(i + 1, arr[i]);
    }
    
    void update(int i, long long delta) {
        for (; i <= n; i += i & -i)
            tree[i] += delta;
    }
    
    long long query(int i) {
        long long sum = 0;
        for (; i > 0; i -= i & -i)
            sum += tree[i];
        return sum;
    }
    
    long long rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

// 2D Fenwick Tree
// Related LeetCode Problems:
// 308. Range Sum Query 2D - Mutable
// https://leetcode.com/problems/range-sum-query-2d-mutable/
// 850. Rectangle Area II
// https://leetcode.com/problems/rectangle-area-ii/
// 699. Falling Squares
// https://leetcode.com/problems/falling-squares/
// 715. Range Module
// https://leetcode.com/problems/range-module/
// 1222. Queens That Can Attack the King
// https://leetcode.com/problems/queens-that-can-attack-the-king/
// 1329. Sort the Matrix Diagonally
// https://leetcode.com/problems/sort-the-matrix-diagonally/
// 1878. Get Biggest Three Rhombus Sums in a Grid
// https://leetcode.com/problems/get-biggest-three-rhombus-sums-in-a-grid/
// 2536. Increment Submatrices by One
// https://leetcode.com/problems/increment-submatrices-by-one/
class FenwickTree2D {
    vector<vector<long long>> tree;
    int n, m;
    
public:
    FenwickTree2D(int n, int m) : n(n), m(m), tree(n + 1, vector<long long>(m + 1, 0)) {}
    
    void update(int x, int y, long long delta) {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= m; j += j & -j)
                tree[i][j] += delta;
    }
    
    long long query(int x, int y) {
        long long sum = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                sum += tree[i][j];
        return sum;
    }
    
    long long rangeQuery(int x1, int y1, int x2, int y2) {
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

// Range Update Fenwick Tree (using difference array)
// Related LeetCode Problems:
// 370. Range Addition
// https://leetcode.com/problems/range-addition/
// 598. Range Addition II
// https://leetcode.com/problems/range-addition-ii/
// 1109. Corporate Flight Bookings
// https://leetcode.com/problems/corporate-flight-bookings/
// 1094. Car Pooling
// https://leetcode.com/problems/car-pooling/
// 1526. Minimum Number of Increments on Subarrays to Form a Target Array
// https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
// 2251. Number of Flowers in Full Bloom
// https://leetcode.com/problems/number-of-flowers-in-full-bloom/
// 2536. Increment Submatrices by One
// https://leetcode.com/problems/increment-submatrices-by-one/
class RangeUpdateFenwick {
    FenwickTree ft;
    
public:
    RangeUpdateFenwick(int n) : ft(n) {}
    
    void rangeUpdate(int l, int r, long long delta) {
        ft.update(l, delta);
        ft.update(r + 1, -delta);
    }
    
    long long pointQuery(int i) {
        return ft.query(i);
    }
};

// Range Update Range Query Fenwick Tree
// Related LeetCode Problems:
// 370. Range Addition
// https://leetcode.com/problems/range-addition/
// 1109. Corporate Flight Bookings
// https://leetcode.com/problems/corporate-flight-bookings/
// 1094. Car Pooling
// https://leetcode.com/problems/car-pooling/
// 1526. Minimum Number of Increments on Subarrays to Form a Target Array
// https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
// 2251. Number of Flowers in Full Bloom
// https://leetcode.com/problems/number-of-flowers-in-full-bloom/
// 2536. Increment Submatrices by One
// https://leetcode.com/problems/increment-submatrices-by-one/
// 1622. Fancy Sequence
// https://leetcode.com/problems/fancy-sequence/
// 2286. Booking Concert Tickets in Groups
// https://leetcode.com/problems/booking-concert-tickets-in-groups/
class RURQFenwick {
    FenwickTree ft1, ft2;
    int n;
    
public:
    RURQFenwick(int n) : n(n), ft1(n), ft2(n) {}
    
    void rangeUpdate(int l, int r, long long delta) {
        ft1.update(l, delta);
        ft1.update(r + 1, -delta);
        ft2.update(l, delta * (l - 1));
        ft2.update(r + 1, -delta * r);
    }
    
    long long prefixQuery(int i) {
        return ft1.query(i) * i - ft2.query(i);
    }
    
    long long rangeQuery(int l, int r) {
        return prefixQuery(r) - prefixQuery(l - 1);
    }
};

// Fenwick Tree for Maximum (using coordinate compression)
// Related LeetCode Problems:
// 239. Sliding Window Maximum
// https://leetcode.com/problems/sliding-window-maximum/
// 699. Falling Squares
// https://leetcode.com/problems/falling-squares/
// 715. Range Module
// https://leetcode.com/problems/range-module/
// 732. My Calendar III
// https://leetcode.com/problems/my-calendar-iii/
// 850. Rectangle Area II
// https://leetcode.com/problems/rectangle-area-ii/
// 1353. Maximum Number of Events That Can Be Attended
// https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
// 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits
// https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/
// 2286. Booking Concert Tickets in Groups
// https://leetcode.com/problems/booking-concert-tickets-in-groups/
class MaxFenwick {
    vector<int> tree;
    int n;
    
public:
    MaxFenwick(int n) : n(n), tree(n + 1, INT_MIN) {}
    
    void update(int i, int val) {
        for (; i <= n; i += i & -i)
            tree[i] = max(tree[i], val);
    }
    
    int query(int i) {
        int maxVal = INT_MIN;
        for (; i > 0; i -= i & -i)
            maxVal = max(maxVal, tree[i]);
        return maxVal;
    }
};

// Inversion Count using Fenwick Tree
// Related LeetCode Problems:
// 315. Count of Smaller Numbers After Self
// https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// 493. Reverse Pairs
// https://leetcode.com/problems/reverse-pairs/
// 327. Count of Range Sum
// https://leetcode.com/problems/count-of-range-sum/
// 1395. Count Number of Teams
// https://leetcode.com/problems/count-number-of-teams/
// 1649. Create Sorted Array through Instructions
// https://leetcode.com/problems/create-sorted-array-through-instructions/
// 2179. Count Good Triplets in an Array
// https://leetcode.com/problems/count-good-triplets-in-an-array/
// 2426. Number of Pairs Satisfying Inequality
// https://leetcode.com/problems/number-of-pairs-satisfying-inequality/
// 2659. Make Array Empty
// https://leetcode.com/problems/make-array-empty/
long long inversionCount(vector<int>& arr) {
    vector<int> sorted = arr;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    auto compress = [&](int x) {
        return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
    };
    
    FenwickTree ft(sorted.size());
    long long inversions = 0;
    
    for (int i = arr.size() - 1; i >= 0; i--) {
        int compressed = compress(arr[i]);
        inversions += ft.query(compressed - 1);
        ft.update(compressed, 1);
    }
    
    return inversions;
}

// Count smaller elements after self
// Related LeetCode Problems:
// 315. Count of Smaller Numbers After Self
// https://leetcode.com/problems/count-of-smaller-numbers-after-self/
// 493. Reverse Pairs
// https://leetcode.com/problems/reverse-pairs/
// 327. Count of Range Sum
// https://leetcode.com/problems/count-of-range-sum/
// 1395. Count Number of Teams
// https://leetcode.com/problems/count-number-of-teams/
// 1649. Create Sorted Array through Instructions
// https://leetcode.com/problems/create-sorted-array-through-instructions/
// 2179. Count Good Triplets in an Array
// https://leetcode.com/problems/count-good-triplets-in-an-array/
// 2426. Number of Pairs Satisfying Inequality
// https://leetcode.com/problems/number-of-pairs-satisfying-inequality/
// 2659. Make Array Empty
// https://leetcode.com/problems/make-array-empty/
vector<int> countSmaller(vector<int>& nums) {
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    
    auto compress = [&](int x) {
        return lower_bound(sorted.begin(), sorted.end(), x) - sorted.begin() + 1;
    };
    
    FenwickTree ft(sorted.size());
    vector<int> result(nums.size());
    
    for (int i = nums.size() - 1; i >= 0; i--) {
        int compressed = compress(nums[i]);
        result[i] = ft.query(compressed - 1);
        ft.update(compressed, 1);
    }
    
    return result;
}

// Range Minimum Query using Fenwick Tree (with coordinate compression)
// Related LeetCode Problems:
// 239. Sliding Window Maximum
// https://leetcode.com/problems/sliding-window-maximum/
// 699. Falling Squares
// https://leetcode.com/problems/falling-squares/
// 715. Range Module
// https://leetcode.com/problems/range-module/
// 732. My Calendar III
// https://leetcode.com/problems/my-calendar-iii/
// 850. Rectangle Area II
// https://leetcode.com/problems/rectangle-area-ii/
// 1353. Maximum Number of Events That Can Be Attended
// https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
// 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits
// https://leetcode.com/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/
// 2286. Booking Concert Tickets in Groups
// https://leetcode.com/problems/booking-concert-tickets-in-groups/
class RMQFenwick {
    vector<int> tree;
    int n;
    
public:
    RMQFenwick(int n) : n(n), tree(n + 1, INT_MAX) {}
    
    void update(int i, int val) {
        for (; i <= n; i += i & -i)
            tree[i] = min(tree[i], val);
    }
    
    int query(int i) {
        int minVal = INT_MAX;
        for (; i > 0; i -= i & -i)
            minVal = min(minVal, tree[i]);
        return minVal;
    }
    
    void reset() {
        fill(tree.begin(), tree.end(), INT_MAX);
    }
};