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 <stdio.h>
2#include <stdlib.h>
3
4#define MAX 100000
5
6int bit[MAX + 1];
7int* getCounts(int* nums, int numsSize, int* returnSize) {
8 *returnSize = numsSize;
9 int* result = (int*) calloc(numsSize, sizeof(int));
10 int minVal = -10000, maxVal = 10000;
11
12 for (int i = numsSize - 1; i >= 0; i--) {
13 int index = nums[i] - minVal + 1;
14 int sum = 0, j = index - 1;
15 while (j > 0) {
16 sum += bit[j];
17 j -= (j & -j);
18 }
19 result[i] = sum;
20 j = index;
21 while (j <= MAX) {
22 bit[j]++;
23 j += (j & -j);
24 }
25 }
26 return result;
27}
28
29int main() {
30 int nums[] = {5, 2, 6, 1};
31 int numsSize = sizeof(nums) / sizeof(nums[0]);
32 int returnSize;
33 int* counts = getCounts(nums, numsSize, &returnSize);
34 for (int i = 0; i < returnSize; i++) {
35 printf("%d ", counts[i]);
36 }
37 free(counts);
38 return 0;
39}This C program uses a static array to represent a Binary Indexed Tree, or Fenwick Tree. It processes each element of the array from right to left and maintains cumulative frequencies of numbers within the bounds. First, it retrieves the cumulative frequency up to one less than the current index using the BIT, which gives the count of numbers less than the current number. Then, it updates the BIT with the frequency of the current number.
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.
1
Using a BST, this Python solution integrates a TreeNode class to capture the node value and left subtree count. Recursive insert operations enable the computation of smaller elements using the pre_sum array, with insertion following the tree structure rules to balance the BST throughout traversal.