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.
1#include <vector>
2#include <iostream>
3using namespace std;
4
5class BIT {
6 vector<int> tree;
7public:
8 BIT(int size) : tree(size + 1, 0) {}
9 void update(int index, int value) {
10 while (index < tree.size()) {
11 tree[index] += value;
12 index += index & -index;
13 }
14 }
15 int query(int index) {
16 int sum = 0;
17 while (index > 0) {
18 sum += tree[index];
19 index -= index & -index;
20 }
21 return sum;
22 }
23};
24
25vector<int> countSmaller(vector<int>& nums) {
26 int offset = 10000; // Offset negative indices
27 int size = 20001; // Total possible discrete values
28 BIT bit(size);
29 vector<int> result(nums.size());
30 for (int i = nums.size() - 1; i >= 0; --i) {
31 result[i] = bit.query(nums[i] + offset);
32 bit.update(nums[i] + offset + 1, 1);
33 }
34 return result;
35}
36
37int main() {
38 vector<int> nums = {5, 2, 6, 1};
39 vector<int> result = countSmaller(nums);
40 for (int num : result) {
41 cout << num << " ";
42 }
43 return 0;
44}This C++ implementation uses a class-based approach for the Binary Indexed Tree. It employs an offset to handle negative numbers smoothly by shifting all indices to be non-negative. It processes each number from right to left in the input list, uses the BIT to fetch the count of numbers smaller than the current number, and updates the BIT to include the current number moving forward.
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.
using System.Collections.Generic;
class Solution {
public class TreeNode {
public int val, leftCount, dup;
public TreeNode left, right;
public TreeNode(int v) {
val = v;
leftCount = 0;
dup = 1;
}
}
public IList<int> CountSmaller(int[] nums) {
List<int> result = new List<int>(new int[nums.Length]);
TreeNode root = null;
for (int i = nums.Length - 1; i >= 0; i--) {
int[] preSum = {0};
root = Insert(root, nums[i], preSum);
result[i] = preSum[0];
}
return result;
}
private TreeNode Insert(TreeNode node, int val, int[] preSum) {
if (node == null) {
return new TreeNode(val);
} else if (node.val == val) {
node.dup++;
preSum[0] += node.leftCount;
} else if (node.val > val) {
node.leftCount++;
node.left = Insert(node.left, val, preSum);
} else {
preSum[0] += node.dup + node.leftCount;
node.right = Insert(node.right, val, preSum);
}
return node;
}
static void Main() {
Solution solution = new Solution();
int[] nums = {5, 2, 6, 1};
IList<int> result = solution.CountSmaller(nums);
Console.WriteLine(string.Join(" ", result));
}
}This C# program deploys a TreeNode that tracks duplicate counts and tree structure, allowing for integrity in traversal while accumulating occurrences of numbers smaller than the current particular element. Insert efficiency is achieved as seen within the problem requirements, substantiated by the preSum reusable variable designed throughout the recursive insert method.