Sponsored
Sponsored
The Binary Indexed Tree (BIT) allows us to efficiently update elements and calculate cumulative frequencies in an iterative manner. In this approach, we traverse the input array from right to left, update the BIT with the index of the current number, and use the BIT to find the count of numbers which are smaller.
Time Complexity: O(n log n), where n is the number of elements in nums. Updating the BIT and querying both take O(log n) time.
Space Complexity: O(n) for the BIT and result array.
1class FenwickTree:
2 def __init__(self, size):
3 self.tree = [0] * (size + 1)
4 def update(self, index, value):
5 while index < len(self.tree):
6 self.tree[index] += value
7 index += index & -index
8 def query(self, index):
9 sum = 0
10 while index > 0:
11 sum += self.tree[index]
12 index -= index & -index
13 return sum
14
15def countSmaller(nums):
16 offset = 10000
17 size = 20001
18 bit = FenwickTree(size)
19 result = [0] * len(nums)
20 for i in range(len(nums)-1, -1, -1):
21 result[i] = bit.query(nums[i] + offset)
22 bit.update(nums[i] + offset + 1, 1)
23 return result
24
25nums = [5, 2, 6, 1]
26print(countSmaller(nums))This Python script implements the Binary Indexed Tree through a FenwickTree class. By applying an offset to the input values, it ensures all indices used with the BIT are positive. By iterating from right to left over the input list, it queries the BIT for the number of less-than elements and updates the current element into the BIT.
This approach takes advantage of the divide and conquer strategy combined with a binary search tree (BST). As we process each number from right to left, we insert them into the BST, which allows us to compute the count of elements smaller than the current number efficiently.
Time Complexity: O(n log n) on average, assuming balanced inserts into the BST.
Space Complexity: O(n) for storing BST nodes and result array.
#include <iostream>
class Solution {
private:
struct TreeNode {
int val, leftCount, count;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), leftCount(0), count(1), left(NULL), right(NULL) {}
};
TreeNode* insert(TreeNode* root, int val, int* preSum) {
if (!root) {
root = new TreeNode(val);
} else if (val == root->val) {
root->count++;
*preSum += root->leftCount;
} else if (val < root->val) {
root->leftCount++;
root->left = insert(root->left, val, preSum);
} else {
*preSum += root->count + root->leftCount;
root->right = insert(root->right, val, preSum);
}
return root;
}
public:
std::vector<int> countSmaller(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n, 0);
TreeNode* root = NULL;
for (int i = n - 1; i >= 0; --i) {
int preSum = 0;
root = insert(root, nums[i], &preSum);
result[i] = preSum;
}
return result;
}
};
int main() {
Solution solution;
std::vector<int> nums = {5, 2, 6, 1};
std::vector<int> result = solution.countSmaller(nums);
for (int count : result) {
std::cout << count << " ";
}
return 0;
}In this C++ implementation, we define a TreeNode struct to manage each node in the BST. The tree is built such that it keeps track of the count of numbers inserted against the left subtree. This effectively allows us to determine the number of smaller previously-inserted numbers relative to each value, yielding the required result.