Fenwick Tree coding pattern

Limitation with Prefix sum

Prefix Sum Array is a simple data structure used to calculate the sum of elements in a range quickly. However, they have a limitation: updating an element requires recalculating all prefix sums from that element to the end of the array. Query: O(1) & Update: O(n)

How Binary Indexed Trees handle update?

Binary Indexed Trees (BITs), also known as Fenwick Trees, are a data structure that efficiently supports range sum queries and updates on an array. BIT offers a balance between the simplicity of prefix sum arrays and the efficiency of segment trees. It is ideal for dynamic arrays (where elements are updated frequently) or when both range sum queries and updates are required. Query: O(log n) & O(log n)

Fenwick Trees with one extra index Structure

Let’s convert following array into Fenwick tree.

Following is Fenwick tree representation of above array.

1. Fenwick tree will have one more element i.e. we will 11 elements.
2. Above diagram is just a tree representation, but actual Fenwick tree is stored as array.
3. 0 is a dummy node and doesn’t store any information.
4. Rest of the node 1 to 11 will store the prefix sum.
5. The nodes of the tree show the ranges they cover.

Note: There are Fenwick tree representation of same size as original array as well. But in this post I am going to use n+1 structure to keep it generic.

How to find out parent of node x?

First find out binary representation of x then flip the rightmost set bit to become y will be parent of x.

Node  Binary  FlipRightmostBit Parent
1     0001    0000              0
2     0010    0000              0
3     0011    0010              2
4     0100    0000              0
5     0101    0100              4
6     0110    0100              4
7     0111    0110              6
8     1000    0000              0
9     1001    1000              8
10    1010    1000              8 
11    1011    1010              10

How to get the parent efficiently?

1. Get 2’s complement of i i.e. -i

2. And it with original index i.e. i&(-i)

3. Subtract to with original index i.e. i-i&(-i)

Following are example to get the parent.

Node  Binary    2'sComponent(-i)   i&(-i)  i-i&(-i)  Parent
1     00000001    11111111       00000001  00000000   0
2     00000010    11111110       00000010  00000000   0
3     00000011    11111101       00000001  00000010   2 
4     00000100    11111100       00000100  00000000   0
5     00000101    11111011       00000001  00000100   4
6     00000110    11111010       00000010  00000100   4
7     00000111    11111001       00000001  00000110   6
8     00001000    11111000       00001000  00000000   0
9     00001001    11110111       00000001  00001000   8
10    00001010    11110110       00000010  00001000   8
11    00001011    11110101       00000001  00001010   10

How to fill the Fenwick tree?

Update the given index and the next node until not exceeded the limit.

1. Get 2’s complement of i i.e. -i
2. and with original number i.e. i&-i
3. Add to original index i.e. i+i&-i

Use above to keep updating tree value for given index.

1. 0 does store anything so we can skip it.
2. For index i=0 we need to update 1 index in tree. Updating 1 is not enough, we will need to update all the other node which could be affected.
3. To get those nodes, we will use getNext() formula as describe above and keep updating until exceeded the limit.
4. Now we need to perform index i=1 in similar fashion

Following is next node conversion.

Node  Binary    2'sComponent(-i)   i&(-i)  i+i&(-i)  Next
1     00000001    11111111       00000001  00000010   2
2     00000010    11111110       00000010  00000100   4
3     00000011    11111101       00000001  00000100   4
4     00000100    11111100       00000100  00001000   8
5     00000101    11111011       00000001  00000110   6
6     00000110    11111010       00000010  00001000   8
7     00000111    11111001       00000001  00001000   8
8     00001000    11111000       00001000  00010000   16
9     00001001    11110111       00000001  00001010   10
10    00001010    11110110       00000010  00001100   12
11    00001011    11110101       00000001  00001100   12

Following is updated tree

How to run query?

For given query(0,5) on original array, we need to go to index 6 in the Fenwick tree. Total sum starting from node 6 and all it’s parent will give the prefix sum for query(0,5) i.e. 9+10=19

Why it works?

If you see carefully, node 6 stores prefix sum for (4,5) . It’s parent node 4 represents prefix sum for (0,3) therefore it make sense to add both to get prefix sum for (0,5)

How to run update?

To update, first find out the delta between original value and new value. Use the delta value to update the rest of the tree as per logic discussed above.

Partial sum based Fenwick Tree

Each node in Fenwick tree will hold the partial sum for the range they cover. This is used for following.

1. query(i) to return the sum of elements from 0...i in original array.
2. query(i,j) to return the sum of elements from i...j in original array.
3. update(i,value) update the ith element in original array for the given value

Following is code for reference.

#include <bits/stdc++.h>
using namespace std;
class FanwikTree {
    private:
        vector<int> tree;
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i += i & (-i);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i > 0) {
            sum += tree[i];
            i -= i & (-i);
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
    public:
    FanwikTree(vector<int> & input) {
        tree.resize(input.size() + 1, 0);
        for(int i=1; i < input.size() + 1; i++) {
            update(i, input[i-1]);
        }
    }
    int rangeQuery(int i, int j) {
        return query(i+1, j+1);
    }
    void update(vector<int> & input, int i, int value) {
        int diff = value - input[i];
        input[i] = value;
        update(i+1, diff);
    }
};
int main() {
    vector<int> input = {1,2,3,4,5};
    FanwikTree tree(input);
    cout << "input array: {1,2,3,4,5}" << endl;
    cout <<"query(3,4)="<< tree.rangeQuery(3,4) << endl;
    cout <<"update(3,6)" << endl;
    tree.update(input, 3, 6);
    cout << "query(3,4)=" << tree.rangeQuery(3,4) << endl;
    return 0;
}

Fenwick Tree of same size

Suppose we have an array of integers A[0,...,n-1] . A Fenwick tree is an array representation of tree T[0,...n-1] , where each element is equal to the sum of elements of A in some range [g(i),i] .

Definition of g(i)

We replace all trailing 1 bit in the binary representation of i with 0 bits.

In other words, if the least significant digit of i in binary is 0 then g(i)=i . Otherwise, if the least significant digit is 1 then we take this 1 and all other trailing 1 and flip them.

There exists a simple implementation using bitwise operations for the non-trivial operation described above:

g(i)=i&(i+1)

i     Binary      i+1            i&(i+1)    g(i)
0     00000000    00000001       00000000    0
1     00000001    00000010       00000000    0
2     00000010    00000011       00000010    2
3     00000011    00000100       00000000    0
4     00000100    00000101       00000100    4
5     00000101    00000110       00000100    4
6     00000110    00000111       00000110    6
7     00000111    00001000       00000000    0
8     00001000    00001001       00001000    8

Following is updated code for query

    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i= (i & (i + 1)) - 1
        }
        return sum;
    }

Now, we just need to find a way to iterate over all j such that g(j)<=i<=j . Unsurprisingly, there also exists a simple way to perform h using bitwise operation as below.

h(j) = j | (j+1)

j     Binary      j+1            j |(j+1)    h(i)
0     00000000    00000001       00000001    1
1     00000001    00000010       00000011    3
2     00000010    00000011       00000011    3
3     00000011    00000100       00000111    7
4     00000100    00000101       00000111    7
5     00000101    00000110       00000111    7
6     00000110    00000111       00000111    7
7     00000111    00001000       00001111    15
8     00001000    00001001       00001001    9

Following is code to use h(i) as below.

    void update(int i, int delta) {
        while (i < n)
            tree[i] += delta;
            i = i | (i + 1)
    }

The following image shows a possible interpretation of the Fenwick tree as tree. The nodes of the tree show the ranges they cover.

Note: Green color represent Fenwick tree index and gray color represent original array.

Pattern #1: Value based Fenwick tree

Following is complete Fenwick tree code template based on element value.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

int main() {
    vector<int> input = {6,9,1,8,4};
    // Build Fenwick tree
    FanwikTree tree(input.size());
    for(int i=0; i < input.size(); i++) {
        tree.update(i, input[i]);
    }
    cout << "query(2,4):" << tree.query(2,4) << endl; // cout 13
    tree.update(2, 3); // update 2nd index with delta 3
    cout << "After update query(2,4):" << tree.query(2,4) << endl; // cout 16
    return 0;
}

Pattern #2: Frequency based Fenwick Tree

This is used to count elements less than a given value.

1. Count the number of elements less than or equal to x
2. Count the number of elements between x and y

Let’s try to build tree with assumption that input array have only positive and unique elements.

1. Find out the max value in the input array.
2. We will use MAX_VALUE+1 as size of Fenwick tree.
3. Here index in tree will represent the all possible elements.
4. Each element’s weight be considered as 1 therefore partial sum will be nothing but counting the frequency.

Note: Since here every node represent the index of original array value therefore update is not suitable for this pattern.

Following is code for reference.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

int main() {
    vector<int> input = {6,9,1,8,4};
    // Build Fenwick tree with frequency
    int MAX_SIZE = *max_element(input.begin(), input.end());
    FanwikTree tree(MAX_SIZE+1);
    for(int i=0; i < input.size(); i++) {
        tree.update(input[i], 1);
    }
    cout << "query(9):" << tree.query(9) << endl; // cout 5
    cout << "query(6,9):" << tree.query(6,9) << endl; // cout 3
    return 0;
}

Pattern #3: Frequency based Fenwick Tree with co-ordinate compression

Given that arr[i] values can be very large, directly using them as indices in the BIT would be inefficient for frequency-based BIT.

We can compress the values of arr to a smaller range [0, N-1] where N is the length of the array.

Consider following input as an example

N = 5
arr = [8, 4, 2, 1, 3]

Step 1: Coordinate Compression

The goal of coordinate compression is to map the values of arr to a smaller range [0, N-1] while preserving the relative order.

1.1 Create a Sorted Copy of arr

- Original `arr = [8, 4, 2, 1, 3]`
- Create a sorted copy of `arr`: `sortedArr = [1, 2, 3, 4, 8]`

1.2 Map Original Values to Compressed Values

We map each element of arr to its index in the sorted array.

Note: Remove consecutive duplicates before this operation.

- `8` → `4`
- `4` → `3`
- `2` → `1`
- `1` → `0`
- `3` → `2`

Thus, the compressed version of arr is:

compressedArr = [4,3,1,0,2]

Example Trace with Duplicates

N = 6
arr = [4, 3, 4, 2, 2, 1]
sortedArr = [1, 2, 3, 4] // Removed consecutive duplicates
- `4` → `3`
- `3` → `2`
- `4` → `3` (same as before, since duplicates map to the same compressed value)
- `2` → `1`
- `2` → `1` (same as before, due to duplicate)
- `1` → `0`
compressedArr = [3, 2, 3, 1, 1, 0]

Following is code for reference.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

int main() {
    vector<int> input = {4, 3, 4, 2, 2, 1};
    // Build Fenwick tree with frequency
    vector<int> sortedArray = input;
    sort(sortedArray.begin(), sortedArray.end());
    sortedArray.erase(unique(sortedArray.begin(), sortedArray.end()), sortedArray.end());
    unordered_map<int, int> array_map;
    for(int i=0; i < sortedArray.size(); i++) {
        array_map[sortedArray[i]] = i;
    }

    FanwikTree tree(sortedArray.size());
    // Insert elements using compressed indices
    for(int i=0; i < input.size(); i++) {
        int compressedIndex = array_map[input[i]];
        tree.update(compressedIndex, 1);
    }
    cout << "query(4):" << tree.query(array_map[4]) << endl; // cout 6
    cout << "query(3,4):" << tree.query(array_map[3],array_map[4]) << endl; // cout 3
    return 0;
}

Pattern #4: Use co-ordinate compression to answer Sum of elements ≤ xx

We can use same co-ordinate compression to answer sum of elements less than or equal to given x . Instead of 1 we need to update input[i] to the Fenwick tree as below.

tree.update(compressedIndex, input[i]);

Following is full code with just above modification.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

int main() {
    vector<int> input = {4, 3, 4, 2, 2, 1};
    // Build Fenwick tree with frequency
    vector<int> sortedArray = input;
    sort(sortedArray.begin(), sortedArray.end());
    sortedArray.erase(unique(sortedArray.begin(), sortedArray.end()), sortedArray.end());
    unordered_map<int, int> array_map;
    for(int i=0; i < sortedArray.size(); i++) {
        array_map[sortedArray[i]] = i;
    }

    FanwikTree tree(sortedArray.size());
    // Insert elements using compressed indices
    for(int i=0; i < input.size(); i++) {
        int compressedIndex = array_map[input[i]];
        tree.update(compressedIndex, input[i]);
    }
    cout << "query(4):" << tree.query(array_map[4]) << endl; // cout 16
    cout << "query(3,4):" << tree.query(array_map[3],array_map[4]) << endl; // cout 11
    return 0;
}

Pattern #5: Extra size Fenwick tree to implement MRU Queue

The MRU Queue is a data structure where elements are moved to the front of the queue when they are accessed (i.e., recently used).

Access: It involves following operations.

1. Finding the current position of an element.
2. Removing the element from its current position.
3. Placing it at the front of the queue.

Challenges

• Dynamic Position Management: As elements are accessed, their positions change dynamically. Keeping track of where each element is located in a sequence is crucial.
• Efficient Query and Update: Each time we access an element, we need to efficiently query its current position and then move it to a new position.

How to use Fenwick tree for MRU Queue?

Fenwick tree with co-ordinate compression gives a mechanism to dynamically update the position of element.

How to move element to first position?

For given element with index i we need to move it to position 0 can be done in following steps.

1. Update ith position as -1 to null and void contribution of ith element.
2. Update element index at 0th position.

Oopps, #2 will override the existing element at 0th position :-(

To handle this, we need allocate extra indices for all the queried element. 1

1. Let’s say if n is size of queries then we can build Fenwick tree of size n+m
2. Reserve n+i to n+m-1 where i=0...m-1 position for original array with size m
3. Every time we run Fenwick query for element let’s say x=queries[i] as query(x), it will count of all elements less than or equal to x .
4. Find the position pos=map[x] for the co-ordinate compression.
5. Since we start with sorted original array therefore in the beginning query(pos) will return the count of x let’s say count
6. We will capture result as count -1 as index for element.
7. Now we will start placing each queried element in the first block of size n with end i.e. n-i-1
8. We will first run update(pos,-1) to undo the contribution of element x
9. Then will move element to position n-i-1 to allocate the index which will always be lower than original pos by calling update(n-j,1)

Extra Size of Fenwick tree a concern?

Only unnatural concept here is to include the size of. This is not ok to use it on production code as size of queries can be very large or unbounded. But ok to solve coding problem here.

Following is code to impelement this approach.

class FanwikTree {
private:
    vector<int> tree;

public:
    FanwikTree(int n) { tree.resize(n, 0); }
    void update(int i, int value) {
        while (i < tree.size()) {
            tree[i] += value;
            i = i | (i + 1);
        }
    }
    int query(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
    int query(int i, int j) { return query(j) - query(i - 1); }
};
class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int n = queries.size();
        vector<int> result(n, -1);
        unordered_map<int, int> array_map;
        FanwikTree tree(n + m);
        // Step 1: Initialize map and Fenwick tree  of size n+m
        for (int i = 0; i < m; i++) {
            array_map[i + 1] = n + i; // numbers are i+1
            tree.update(n + i, 1);    // Frequency update
        }
        // Step 2: Process each query
        for (int i = 0; i < n; i++) {
            int element = queries[i];
            int pos = array_map[element];
            // Query the BIT to find how many elements are to the left of the
            // current position
            cout << endl;
            int count = tree.query(pos);
            result[i] = count - 1; // 0th based index
            // Move the queried element to the front of the permutation
            // (position n - i)
            tree.update(pos, -1);
            array_map[element] = n - i -1; // update elememt's new pos
            tree.update(array_map[element], 1);
        }
        return result;
    }
};

Pattern #6: Get min or max for given range using Fenwick tree

Fenwick tree is not suitable to find min/max for the given range. It can only find if running query(i) i.e min or max between 0...i . Not for query(i,j) .

Segment tree is more suitable for this problem.

Pattern #7: 2D-Fenwick tree

A 2D BIT (Fenwick Tree) is an extension of the 1D BIT that allows us to efficiently process range queries and updates in a 2D grid. It is particularly useful when dealing with problems that involve 2D grids (like matrices) and where we need to perform operations such as:

• Querying the sum of elements in a rectangular submatrix.
• Updating an element in a matrix and propagating that change to the rest of the grid.

Key Operations in 2D BIT

Just like with a 1D BIT, a 2D BIT supports two main operations:

1. Update (x, y, delta): Update the value at position (x, y) in the matrix by adding delta.
2. Query (x, y): Query the sum of elements from (1,1) to (x, y) in the matrix.

Structure of 2D BIT

A 2D BIT is conceptually a 2D array where each element of the array represents a sum of values over a specific rectangular region of the grid.

Just like in the 1D BIT, the indices are represented in binary, and the sum of elements in a region is stored and updated using the binary indexed structure.

The 2D BIT stores cumulative sums of the matrix elements. For example, in a grid of size N x M, the BIT at position (x, y) stores the cumulative sum of the submatrix from (0,0) to (x, y).

Update operation

void update(int row, int col, int delta) {
    for (int i = row; i < m; i = (i | (i + 1))) {
        for (int j = col; j < n; j = (j | (j + 1))) {
            tree[i][j] += delta;
        }
    }
}

Query operation

int query(int row, int col) {
    int ans = 0;
    for (int i = row; i >= 0; i = (i & (i + 1)) - 1) {
        for (int j = col; j >= 0; j = (j & (j + 1)) - 1) {
            ans += tree[i][j];
        }
    }
    return ans;
}

Range sum query

int sumRegion(int row1, int col1, int row2, int col2) {
    return tree.query(row2, col2) - tree.query(row1 - 1, col2) -
           tree.query(row2, col1 - 1) + tree.query(row1 - 1, col1 - 1);
}

Let’s solve problem using Fenwick tree

3109. Find the Index of Permutation

https://leetcode.com/problems/find-the-index-of-permutation/description/

Given an array perm of length n which is a permutation of [1, 2, ..., n], return the index of perm in the lexicographically sorted array of all of the permutations of [1, 2, ..., n].

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: perm = [1,2]
Output: 0
Explanation:
There are only two permutations in the following order:
[1,2], [2,1]
And [1,2] is at index 0.

Example 2:

Input: perm = [3,1,2]
Output: 4
Explanation:
There are only six permutations in the following order:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
And [3,1,2] is at index 4.

Constraints:

• 1 <= n == perm.length <= 105
• perm is a permutation of [1, 2, ..., n].

Approach 1(TLE)# Use Recursion with memoization

Let’s print all possible permutation for given set[1,2,3] with target [3,1,2]

123 0
132 1
213 2
231 3
312 4 -- target
321 5

Following is to count the number of permutation.

f(n)=n*f(n-1)

It means, at 0th position we have n choices to choose element. Once we choose number then for rest we will have n-1 choices available.

Since we are generating permutations in increasing order therefore once we choose x then rest of the digits must be greater than x to maintain the increasing order.

Also, if x is placed on ith position it means fact(n-i-1)*count_elem_less_than_x is already generated.

Based on this, we can write following recursion relationship.

f(i)= Count of permuations generated before placing ith digit
xxxxixxx i.e. how many permutations are generated before ith elem.
f(i) = fact(n-i-1)*count_less_than(i) + f(i+1)
f(0) should give the answer based on above. 

We can reverse the recursion as following as well
f(i) = fact(n-i-1)*count_less_than(i) + f(i-1)
Then f(n-1) should gives the answer

Following is code for reference.

class Solution {
private:
    int MOD = pow(10, 9) + 7;
    vector<long> dp;

public:
    int fact(long n) {
        if (n <= 1) {
            return 1;
        }
        if(dp[n] != -1) {
            return dp[n];
        }
        long prev = fact(n - 1) % MOD;
        dp[n] = (n * prev) % MOD;
        return dp[n];
    }
    int count(vector<int>& perm, int i) {
        int n = perm.size();
        int ans = 0;
        for (int j = i + 1; j < n; j++) {
            if (perm[j] < perm[i]) {
                ans++;
            }
        }
        return ans;
    }
    long recur(vector<int>& perm, int i) {
        int n = perm.size();
        if (i == -1) {
            return 0;
        }
        long block = fact(n - 1 - i) % MOD;
        long total = (block * count(perm, i)) % MOD;
        return (total + (recur(perm, i - 1)) % MOD);
    }
    int getPermutationIndex(vector<int>& perm) {
        dp.resize(perm.size() + 1, -1);
        dp[0] = 1;
        dp[1] = 1;
        return recur(perm, perm.size()-1) % MOD;
    }
};

Approach #2: Using Fenwick tree to

In the above code, we can optimize count further if we apply Fenwick tree based on frequency to count the number less than the given element.

But there is one difference, we don’t want to count all the element less than the given number. Instead, we only want to count small elements on the right of given number.

This can be achieved if we build Fenwick tree from right to left and run the query as we build the tree, so that it will gurantee that not to count future result.

Following is code for reference.

// Same size Fenwick tree
class Fenwick {
private:
    vector<int> tree;

public:
    Fenwick(int n) { tree.resize(n, 0); }
    void update(int i, int value) {
        while (i < tree.size()) {
            tree[i] += value;
            i = i | (i + 1);
        }
    }
    int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
};
class Solution {
private:
    int MOD = pow(10, 9) + 7;
    vector<long> dp;

public:
    int fact(long n) {
        if (n <= 1) {
            return 1;
        }
        if (dp[n] != -1) {
            return dp[n];
        }
        long prev = fact(n - 1) % MOD;
        dp[n] = (n * prev) % MOD;
        return dp[n];
    }

    long recur(vector<int>& perm, Fenwick& tree, int i) {
        int n = perm.size();
        if (i == -1) {
            return 0;
        }
        // update tree
        tree.update(perm[i], 1); // frequency
        long block = fact(n - 1 - i) % MOD;
        int count = tree.query(perm[i] - 1);
        long total = (block * count) % MOD;
        return (total + (recur(perm, tree, i - 1)) % MOD);
    }
    int getPermutationIndex(vector<int>& perm) {
        int n = perm.size();
        // Initialie factorial dp
        dp.resize(n + 1, -1);
        dp[0] = 1;
        dp[1] = 1;
        // Build fenwick tree
        int max = *max_element(perm.begin(), perm.end());
        Fenwick tree(max);
        return recur(perm, tree, n - 1) % MOD;
    }
};

Inversion Count

SPOJ.com - Problem INVCNT

Let A[0…n — 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Given n and an array A your task is to find the number of inversions of A.

Input

The first line contains t, the number of testcases followed by a blank space. Each of the t tests start with a number n (n <= 200000). Then n + 1 lines follow. In the ith line a number A[i — 1] is given (A[i — 1] <= 10⁷). The (n + 1)th line is a blank space.

Output

For every test output one line giving the number of inversions of A.

Example

Input:
2
3
3
1
2

5
2
3
8
6
1

Output:
2
5

Approach: Using Fenwick tree

Let’s consider following example.

[3,1,2]

Here (0,1) and (0,2) are two invariant pairs.

Similarly, take following example.

[2,3,8,6,1]

Here (0,4) , (1,4) , (2,4) , (2,3)and (3,4) are invariants.

Fenwick frequency based tree gives count of all the elements less than given number irrespective of location on left or right.

But here we want to count lesser elements on right side only. We can take following approach here.

1. We can build Fenwick tree from right to left.
2. While building the tree for i , we can run the query before we update the i .

Since input are given as positive number therefore we can use with or without co-ordinate compression. For simplicity let’s write code without co-ordinate compression.

Following is code for reference.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

long long solve(vector<int> &input) {
    vector<int> sortedArray = input;
    int MAX_SIZE = *max_element(input.begin(), input.end());

    FanwikTree tree(MAX_SIZE + 1);
    // Insert elements using compressed indices
    long long ans = 0;
    for(int i=input.size()-1; i >=0; i--) {
        int count = tree.query(input[i]);
        if(count > 0) {
            ans += count;
        }
        tree.update(input[i], 1);
    }
    return ans;
}

int main() {
    int t,x;
    cin >> t;
    for (int i=0; i < t; i++) {
        int size;
        cin >> size;
        vector<int> input(size, 0);
        for (int j=0; j < size; j++) {
            cin >> input[j];
        }
        cout<<solve(input) << endl;   
    }
    return 0;
}

We can also write following code with co-ordinate compressor.

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

class FanwikTree {
    private:
        vector<int> tree;
    public:
    FanwikTree(int n) {
        tree.resize(n, 0);
    }    
    void update(int i, int value) {
        while(i < tree.size()) {
            tree[i] += value;
            i = i | (i+1);
        }
    }
    int query(int i) {
        int sum = 0;
        while(i >= 0) {
            sum += tree[i];
            i = (i & (i+1)) -1;
        }
        return sum;
    }
    int query(int i, int j) {
        return query(j) -query(i-1);
    }        
};

long long solve(vector<int> &input) {
    vector<int> sortedArray = input;
    sort(sortedArray.begin(), sortedArray.end());
    sortedArray.erase(unique(sortedArray.begin(), sortedArray.end()), sortedArray.end());
    unordered_map<int, int> array_map;
    for(int i=0; i < sortedArray.size(); i++) {
        array_map[sortedArray[i]] = i;
    }

    FanwikTree tree(sortedArray.size());
    // Insert elements using compressed indices
    long long ans = 0;
    for(int i=input.size()-1; i >=0; i--) {
        int compressedIndex = array_map[input[i]];
        int count = tree.query(compressedIndex -1);
        if(count > 0) {
            ans += count;
        }
        tree.update(compressedIndex, 1);
    }
    return ans;
}

int main() {
    int t,x;
    cin >> t;
    for (int i=0; i < t; i++) {
        int size;
        cin >> size;
        vector<int> input(size, 0);
        for (int j=0; j < size; j++) {
            cin >> input[j];
        }
        cout<<solve(input) << endl;   
    }
    return 0;
}

Note: Since A[i]<=10^7 therefore count can go beyond 10^9 therefore ans as int will overflow. To handle it, we will use long long type for ans

2031. Count Subarrays With More Ones Than Zeros

https://leetcode.com/problems/count-subarrays-with-more-ones-than-zeros/description/

You are given a binary array nums containing only the integers 0 and 1. Return the number of subarrays in nums that have more 1's than 0's. Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [0,1,1,0,1]
Output: 9
Explanation:
The subarrays of size 1 that have more ones than zeros are: [1], [1], [1]
The subarrays of size 2 that have more ones than zeros are: [1,1]
The subarrays of size 3 that have more ones than zeros are: [0,1,1], [1,1,0], [1,0,1]
The subarrays of size 4 that have more ones than zeros are: [1,1,0,1]
The subarrays of size 5 that have more ones than zeros are: [0,1,1,0,1]

Approach# Use Fenwick tree

TBD

315. Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Approach: Use Fenwick tree using frequency

This problem seems exactly same as inversion count. Since input can be negative therefore we need to use co-ordinate compression.

Following is code for reference.

class FanwikTree {
private:
    vector<int> tree;

public:
    FanwikTree(int n) { tree.resize(n, 0); }
    void update(int i, int value) {
        while (i < tree.size()) {
            tree[i] += value;
            i = i | (i + 1);
        }
    }
    int query(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
    int query(int i, int j) { return query(j) - query(i - 1); }
};

class Solution {
private:
    vector<int> solve(vector<int>& input) {
        vector<int> ans(input.size(), 0);
        vector<int> sortedArray = input;
        sort(sortedArray.begin(), sortedArray.end());
        sortedArray.erase(unique(sortedArray.begin(), sortedArray.end()),
                          sortedArray.end());
        unordered_map<int, int> array_map;
        for (int i = 0; i < sortedArray.size(); i++) {
            array_map[sortedArray[i]] = i;
        }

        FanwikTree tree(sortedArray.size());
        // Insert elements using compressed indices
        for (int i = input.size() - 1; i >= 0; i--) {
            int compressedIndex = array_map[input[i]];
            ans[i] = tree.query(compressedIndex-1);
            tree.update(compressedIndex, 1);
        }
        return ans;
    }

public:
    vector<int> countSmaller(vector<int>& nums) { return solve(nums); }
};

1409. Queries on a Permutation With Key

https://leetcode.com/problems/queries-on-a-permutation-with-key/description/

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

• In the beginning, you have the permutation P=[1,2,3,...,m].
• For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].

Approach: Use Fenwick tree with MRU Queue concept

This is implementation of MRU Queue. We can write code as below.

class FanwikTree {
private:
    vector<int> tree;

public:
    FanwikTree(int n) { tree.resize(n, 0); }
    void update(int i, int value) {
        while (i < tree.size()) {
            tree[i] += value;
            i = i | (i + 1);
        }
    }
    int query(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += tree[i];
            i = (i & (i + 1)) - 1;
        }
        return sum;
    }
    int query(int i, int j) { return query(j) - query(i - 1); }
};
class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        int n = queries.size();
        vector<int> result(n, -1);
        unordered_map<int, int> array_map;
        FanwikTree tree(n + m);
        // Step 1: Initialize map and Fenwick tree  of size n+m
        for (int i = 0; i < m; i++) {
            array_map[i + 1] = n + i; // numbers are i+1
            tree.update(n + i, 1);    // Frequency update
        }
        // Step 2: Process each query
        for (int i = 0; i < n; i++) {
            int element = queries[i];
            int pos = array_map[element];
            // Query the BIT to find how many elements are to the left of the
            // current position
            cout << endl;
            int count = tree.query(pos);
            result[i] = count - 1; // 0th based index
            // Move the queried element to the front of the permutation
            // (position n - i)
            tree.update(pos, -1);
            array_map[element] = n - i -1; // update elememt's new pos
            tree.update(array_map[element], 1);
        }
        return result;
    }
};

308. Range Sum Query 2D — Mutable

https://leetcode.com/problems/range-sum-query-2d-mutable/description/

Given a 2D matrix matrix, handle multiple queries of the following types:

1. Update the value of a cell in matrix.
2. Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

• NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
• void update(int row, int col, int val) Updates the value of matrix[row][col] to be val.
• int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:

Input
["NumMatrix", "sumRegion", "update", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [3, 2, 2], [2, 1, 4, 3]]
Output
[null, 8, null, 10]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e. sum of the left red rectangle)
numMatrix.update(3, 2, 2);       // matrix changes from left image to right image
numMatrix.sumRegion(2, 1, 4, 3); // return 10 (i.e. sum of the right red rectangle)

Approach# Using 2d Fenwick pattern

class FenwickTree {
private:
    vector<vector<int>> tree;
    int m;
    int n;

public:
    FenwickTree(int m, int n) {
        tree.assign(m, vector<int>(n, 0));
        this->m = m;
        this->n = n;
    }
    void update(int row, int col, int delta) {
        for (int i = row; i < m; i = (i | (i + 1))) {
            for (int j = col; j < n; j = (j | (j + 1))) {
                tree[i][j] += delta;
            }
        }
    }
    int query(int row, int col) {
        int ans = 0;
        for (int i = row; i >= 0; i = (i & (i + 1)) - 1) {
            for (int j = col; j >= 0; j = (j & (j + 1)) - 1) {
                ans += tree[i][j];
            }
        }
        return ans;
    }
};
class NumMatrix {
private:
    FenwickTree tree;
    vector<vector<int>> matrix;

public:
    NumMatrix(vector<vector<int>>& matrix)
        : tree(matrix.size(), matrix[0].size()) {
        this->matrix = matrix;
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tree.update(i, j, matrix[i][j]);
            }
        }
    }

    void update(int row, int col, int val) {
        tree.update(row, col, val - matrix[row][col]);
        matrix[row][col] = val;
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return tree.query(row2, col2) - tree.query(row1 - 1, col2) -
               tree.query(row2, col1 - 1) + tree.query(row1 - 1, col1 - 1);
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * obj->update(row,col,val);
 * int param_2 = obj->sumRegion(row1,col1,row2,col2);
 */

Enjoy learning :-)