Typical problems of Fenwick Tree (Binary Indexed Tree)
Fenwick Tree (Binary Indexed Tree) is a very typical data structure that has wide applications in both interview questions and algorithm competitions. (If you are not familiar with this data structure, you can check out Fenwick Tree(Binary Indexed Tree) Explained.)
This article will introduce some typical problems of Binary Indexed Tree, mainly from leetcode and codeforces.
For convenience, this article will refer to Fenwick Tree (Binary Indexed Tree) as BIT.
Leetcode 300. Longest Increasing Subsequence
Description of the problem is as follows:
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Constraints: 1 <= nums.length <= 2500, -10000 <= nums[i] <= 10000c
This is a classic Longest Increasing Subsequence (LIS) problem.
The most classic solution is dynamic programming, where f[i] represents the length of the longest increasing subsequence ending with the i-th element, note that nums[i] must be selected:
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
f = [1 for _ in range(n)]
for i in range(1, n):
fj_max = 0
for j in range(i):
if nums[j] < nums[i]:
fj_max = max(fj_max, f[j])
f[i] = fj_max + 1
return max(f)However, the time complexity is O(n²).
Another solution is the greedy + binary search, which can reduce the time complexity to O(n log n). It is not the focus of this article and will not be introduced.
The method introduced in this article is to use data structures to reduce the time complexity.
It is noted that in the second loop of the dynamic programming solution, the task is to traverse the closed interval [0, i-1] for the i-th element, and for each element nums[j] that is less than nums[i], find the maximum value of f[j] (the length of the LIS ending with j):
Traversing one by one in this way has a time complexity of O(n), which is quite time-consuming.
Therefore, if there is a data structure that can quickly query the fj_max in the closed interval [0, i-1] when traversing to nums[i], and quickly store the current f[i] (the length of LIS ending in i) for later queries , the time complexity can be reduced.
Notice that Formula (1) is actually a problem of finding the maximum value in the prefix interval [0, i-1] of the nums array. Considering that prefix sums can be solved using Binary Indexed Tree, we can modify the BIT to support prefix maximum values.
There is a special case in this problem where there are negative numbers, so we need to perform discretization on the nums array, mapping the value range of [-10000, 10000] to [1, 20001]. (If you are not familiar with discretization, please refer to this article: Discretization in the field of algorithms )
After discretizing, the array element id starts from 1. This is because BIT cannot handle update(0, val), code is as follows:
typedef long long ll;
const int N = 1e5 + 7;
struct BIT
{
#define lowbit(x) x & (-x)
ll tree[N];
BIT()
{
memset(tree, 0, sizeof(tree));
}
inline ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res = max(res, tree[x]); // Modify BIT to support querying maximum prefix value
return res;
}
inline void update(int x, ll val) // If x = 0, it will result in an infinite loop because lowbit(0) = 0.
{
for (; x < N; x += lowbit(x))
tree[x] = max(tree[x], val); // Modify BIT to support updating the maximum prefix value
}
};
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
BIT tr;
int res = 0;
vector<int> b = nums;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto get_id = [&](int v) { // Query the 1-indexed rank of nums[i] after discretization.
return lower_bound(b.begin(), b.end(), v) - b.begin() + 1;
};
for (int i = 0; i <= (int)nums.size() - 1; i++)
{
int fj_max = tr.query(get_id(nums[i]) - 1); // Query the fj_max corresponding to nums[i] in O(log n) within the closed interval [0, i-1].
res = max(res, fj_max + 1); // Set f[i] to fj_max + 1 and update the global maximum value.
tr.update(get_id(nums[i]), fj_max + 1); // Store f[i] in O(log n) time complexity.
}
return res;
}
};Time complexity: O(n log n)
Leetcode 493. Reverse Pairs
Description of the problem:
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where: 0 <= i < j < nums.length and nums[i] > 2 * nums[j].
Example 1:
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) → nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) → nums[3] = 3, nums[4] = 1, 3 > 2 * 1
Example 2:
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) → nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) → nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) → nums[3] = 5, nums[4] = 1, 5 > 2 * 1
Constraints:
1 <= nums.length <= 5 * 10⁴
-2³¹ <= nums[i] <= 2³¹ — 1
This problem aims to find the reverse pairs in an array, and it is a typical application of Binary Indexed Tree.
The brute force solution for this problem is:
class Solution:
def reversePairs(self, nums: List[int]) -> int:
res = 0
for j in range(1, len(nums)):
for i in range(j):
if nums[i] > 2 * nums[j]:
res += 1
return resHowever, it is obvious that it will TLE because the length of the array is 1 <= nums.length <= 5 * 10⁴. Therefore, we must look for a solution with lower time complexity.
One solution is to cleverly modify the merge process of merge sort to achieve O(n log n), but this is not the focus of this article and will be explained in the future.
Note that the double loop part of the brute force solution above is similar to the dynamic programming solution of Leetcode 300 we discussed earlier.
However, while Leetcode 300 seeks the maximum value of the prefix interval of the nums array, this problem seeks the total number of prefix intervals [0, j-1] that satisfy the condition in the nums array:
Computing prefix sums is exactly what BIT is good at. You only need to make a few modifications to the Leetcode 300 code:
typedef long long ll;
const int N = 1e5 + 7;
struct BIT
{
#define lowbit(x) x & (-x)
ll tree[N];
BIT()
{
memset(tree, 0, sizeof(tree));
}
inline ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res += tree[x]; // Query prefix sum
return res;
}
inline void update(int x, ll val)
{
for (; x < N; x += lowbit(x))
tree[x] += val; // update
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
BIT tr;
int res = 0;
vector<ll> b; // This problem requires long long
for(auto &x : nums)
b.push_back(x), b.push_back(2 * (ll)x); // Double the value of the element is also added for easy querying
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto get_id = [&](ll v) { // This problem requires long long
return lower_bound(b.begin(), b.end(), v) - b.begin() + 1;
};
// This loop is the main difference with Leetcode 300.
for (int j = 0; j <= (int)nums.size() - 1; j++)
{
// Query the number of nums[i] satisfying nums[i] > 2 * nums[j] in the range [0, j-1].
int cnt_i = tr.query(N - 1) - tr.query(get_id(2 * (ll)nums[j]));
res += cnt_i;
tr.update(get_id(nums[j]), 1);
}
return res;
}
};Time complexity: O(n log n)
Codeforces 627 B. Factory Repairs
Due to the lengthy description of the problem, let’s explain the meaning in simple terms:
There is an array t of length n, and three numbers a, b, k. Initially, each element of the array is 0.
There are q operations, each of which can be one of two types:
1 x y: increase the value of t[x] by y.
2 x: Calculate and output the result of the following formula:
Approach 1: First consider brute force, with O(1) for modification and O(n) for querying.
Approach 2: Use a segment tree or a BIT to maintain this sequence. When encountering the second type of operation, compare them with brute force. However, it is clearly time-consuming and will TLE.
Approach 3: Note that in operation 2, the interval sum of the array needs to be calculated, it is not difficult to think of using two BITs to maintain min(b,t[i]) and min(a,t[i])) respectively. For operation 2, output directly: BIT[0].query(x - 1) + BIT[1].query(N - 1) - BIT[1].query(x + k - 1).
At this point, the efficiency of operation 2 has been reduced to O(log n).
As operation 1 is a single point modification, we can extract the value of the point to be modified directly from the two BITs, which is t[x].
If t[x] + y is less than both a and b, we can simply increment it. Otherwise, we need to modify it to a or b by increasing the point by a — t[x] (or b — t[x]).
Therefore, we need to maintain two BITs that can perform single point modifications and queries. This is a basic operation of BIT.
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int n, k, a, b, m;
struct
{
#define lowbit(x) x & (-x)
ll tree[N];
inline void clear()
{
memset(tree, 0, sizeof(tree));
}
inline ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res += tree[x];
return res;
}
inline void update(int x, ll val)
{
for (; x < N; x += lowbit(x))
tree[x] += val;
}
} BIT[2]; // two BITs
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k >> a >> b >> m;
int opt, x, y;
while (m--)
{
cin >> opt;
if (opt == 1)
{
cin >> x >> y;
int tx_0 = BIT[0].query(x) - BIT[0].query(x - 1);
if (tx_0 + y <= b)
BIT[0].update(x, y); // Can add y
else
BIT[0].update(x, b - tx_0); // If the incremented value is greater than b, then increase it to b.
int tx_1 = BIT[1].query(x) - BIT[1].query(x - 1);
if (tx_1 + y <= a)
BIT[1].update(x, y);// Can add y
else
BIT[1].update(x, a - tx_1); // If the incremented value is greater than a, then increase it to a.
}
else
{
cin >> x;
cout << BIT[0].query(x - 1) + BIT[1].query(N - 1) - BIT[1].query(x + k - 1) << endl;
}
}
return 0;
}Time complexity: O(m log n)
Codeforces 1677 A. Tokitsukaze and Strange Inequality
The description is quite long, here’s a simple explanation:
Given a permutation p of length n, find the number of quadruples (a,b,c,d) such that a < b < c < d and p[a] < p[c], p[b] > p[d].
Approach 1, brute force: Enumerate a, b, c, and d through four nested loops, with a complexity of O(n⁴), which will obviously TLE.
Approach 2, pre-processing: Consider enumerating b and c , with b and c fixed, the answer is transformed into: the number of elements less than p[c] to the left of b multiplied by the number of elements less than p[b] to the right of c.
If we knew these two pieces of information in advance, the time complexity would significantly decrease.
Consider the number of elements less than p[c] to the left of b. The outer loop enumerates b, and the elements to the left of b have already been added to the BIT in advance. The inner loop enumerates c, and uses a two-dimensional array f[b][p[c]] to record the number of elements less than p[c] to the left of b.
The code is as follows:
BIT.clear();
BIT.update(p[1], 1); // First element is not within range of b, so add it first.
for (int b = 2; b <= n - 2; b++) // Enumerate b
{
for (int c = b + 1; c <= n - 1; c++) // Enumerate c
f[b][p[c]] = BIT.query(p[c] - 1); // Number of elements less than p[c] on the left of b
BIT.update(p[b], 1); // Can only join p[b] now because we need to query the left side of b.
}Similar to the above, the number of elements that are smaller than p[b] on the right side of c is recorded using a two-dimensional array g[c][p[b]].
The overall code is as follows:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) x & (-x)
const int N = 5005;
int p[N], f[N][N], g[N][N];
int n, T;
struct
{
ll tree[N];
inline void clear()
{
memset(tree, 0, sizeof(tree));
}
inline ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res += tree[x];
return res;
}
inline void update(int x, ll val)
{
for (; x < N; x += lowbit(x))
tree[x] += val;
}
} BIT;
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
BIT.clear();
BIT.update(p[1], 1); // First element is not within range of b, so add it first.
for (int b = 2; b <= n - 2; b++) // Enumerate b
{
for (int c = b + 1; c <= n - 1; c++) // Enumerate c
f[b][p[c]] = BIT.query(p[c] - 1); // Number of elements less than p[c] on the left of b
BIT.update(p[b], 1); // Can only join p[b] now because we need to query the left side of b.
}
BIT.clear();
BIT.update(p[n], 1); // Last element is not within range of c, so add it first.
for (int c = n - 1; c >= 3; c--) // Enumerate c
{
for (int b = 2; b <= c - 1; b++) // Enumerate b
g[c][p[b]] = BIT.query(p[b] - 1); // Number of elements less than p[b] on the right of c
BIT.update(p[c], 1); // Can only join p[c] now because we need to query the right side of c.
}
ll res = 0;
for (int b = 2; b <= n - 2; b++) // Enumerate b
for (int c = b + 1; c <= n - 1; c++) // Enumerate c
res += f[b][p[c]] * g[c][p[b]];
cout << res << endl;
}
return 0;
}Time complexity: O(n² log n)
Conclusion
Fenwick Tree (Binary Indexed Tree) is a data structure with small code size and fast speed.
It has a wide range of applications in interview questions and algorithm competitions. Some questions specifically test BIT knowledge, while others use BIT as a tool for quickly querying prefix sums or prefix maximum values.
This article introduces several typical example questions of Fenwick Tree (Binary Indexed Tree), and the addresses of these questions will be provided in the reference materials. Interested readers can try them out.
Finally, if there are any omissions or errors in this article, please kindly advise me. Thank you.
References
https://leetcode.com/problems/longest-increasing-subsequence/.
https://leetcode.com/problems/reverse-pairs/
