本期节目中我们介绍了Fenwick Tree/Binary Indexed Tree/树状数组的原理和实现以及它在leetcode中的应用。
In this episode, we will introduce Fenwick Tree/Binary Indexed Tree, its idea and implementation and show its applications in leetcode.

Fenwick Tree is mainly designed for solving the single point update range sum problems. e.g. what’s the sum between i-th and j-th element while the values of the elements are mutable.

Init the tree (include building all prefix sums) takes O(nlogn)

Update the value of an element takes O(logn)

Query the range sum takes O(logn)

Space complexity: O(n)

Applications:

Implementation:

C++

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) {

return x & (-x);

}

vector<int> sums_;

};

Java

class FenwickTree {

int sums_[];

public FenwickTree(int n) {

sums_ = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums_.length) {

sums_[i] += delta;

i += i & -i;

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= i & -i;

}

return sum;

}

Python3

class FenwickTree:

def __init__(self, n):

self._sums = [0 for _ in range(n + 1)]

def update(self, i, delta):

while i < len(self._sums):

self._sums[i] += delta

i += i & -i

def query(self, i):

s = 0

while i > 0:

s += self._sums[i]

i -= i & -i

return s

Applications

题目大意：给你一个数组，对于数组中的每个元素，返回一共有多少在它之后的元素比它小。

Problem:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

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.

Return the array [2, 1, 1, 0].

Idea:

Fenwick Tree / Binary Indexed Tree

BST

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

// Author: Huahua

// Runnning time: 32 ms

// Time complexity: O(nlogn)

// Space complexity: O(k), k is the number unique elements

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) { return x & (-x); }

vector<int> sums_;

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

// Sort the unique numbers

set<int> sorted(nums.begin(), nums.end());

// Map the number to its rank

unordered_map<int, int> ranks;

int rank = 0;

for (const int num : sorted)

ranks[num] = ++rank;

vector<int> ans;

FenwickTree tree(ranks.size());

// Scan the numbers in reversed order

for (int i = nums.size() - 1; i >= 0; --i) {

// Chechk how many numbers are smaller than the current number.

ans.push_back(tree.query(ranks[nums[i]] - 1));

// Increse the count of the rank of current number.

tree.update(ranks[nums[i]], 1);

}

std::reverse(ans.begin(), ans.end());

return ans;

}

};

Java

// Author: Huahua

// Running time: 28 ms

class Solution {

private static int lowbit(int x) { return x & (-x); }

class FenwickTree {

private int[] sums;

public FenwickTree(int n) {

sums = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums.length) {

sums[i] += delta;

i += lowbit(i);

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums[i];

i -= lowbit(i);

}

return sum;

}

};

public List<Integer> countSmaller(int[] nums) {

int[] sorted = Arrays.copyOf(nums, nums.length);

Arrays.sort(sorted);

Map<Integer, Integer> ranks = new HashMap<>();

int rank = 0;

for (int i = 0; i < sorted.length; ++i)

if (i == 0 || sorted[i] != sorted[i - 1])

ranks.put(sorted[i], ++rank);

FenwickTree tree = new FenwickTree(ranks.size());

List<Integer> ans = new ArrayList<Integer>();

for (int i = nums.length - 1; i >= 0; --i) {

int sum = tree.query(ranks.get(nums[i]) - 1);

ans.add(tree.query(ranks.get(nums[i]) - 1));

tree.update(ranks.get(nums[i]), 1);

}

Collections.reverse(ans);

return ans;

}

Solution 2: BST

C++

// Author: Huahua

// Running time: 26 ms

struct BSTNode {

int val;

int count;

int left_count;

BSTNode* left;

BSTNode* right;

BSTNode(int val): val(val), count(1), left_count(0), left{nullptr}, right{nullptr} {}

~BSTNode() { delete left; delete right; }

int less_or_equal() const { return count + left_count; }

};

class Solution {

public:

vector<int> countSmaller(vector<int>& nums) {

if (nums.empty()) return {};

std::reverse(nums.begin(), nums.end());

std::unique_ptr<BSTNode> root(new BSTNode(nums[0]));

vector<int> ans{0};

for (int i = 1; i < nums.size(); ++i)

ans.push_back(insert(root.get(), nums[i]));

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

// Returns the number of elements smaller than val under root.

int insert(BSTNode* root, int val) {

if (root->val == val) {

++root->count;

return root->left_count;

} else if (val < root->val) {

++root->left_count;

if (root->left == nullptr) {

root->left = new BSTNode(val);

return 0;

}

return insert(root->left, val);

} else {

if (root->right == nullptr) {

root->right = new BSTNode(val);

return root->less_or_equal();

}

return root->less_or_equal() + insert(root->right, val);

}

};

Java

// Author: Huahua

// Running time: 10 ms

class Solution {

class Node {

int val;

int count;

int left_count;

Node left;

Node right;

public Node(int val) { this.val = val; this.count = 1; }

public int less_or_equal() { return count + left_count; }

}

public List<Integer> countSmaller(int[] nums) {

List<Integer> ans = new ArrayList<>();

if (nums.length == 0) return ans;

int n = nums.length;

Node root = new Node(nums[n - 1]);

ans.add(0);

for (int i = n - 2; i >= 0; --i)

ans.add(insert(root, nums[i]));

Collections.reverse(ans);

return ans;

}

private int insert(Node root, int val) {

if (root.val == val) {

++root.count;

return root.left_count;

} else if (val < root.val) {

++root.left_count;

if (root.left == null) {

root.left = new Node(val);

return 0;

}

return insert(root.left, val);

} else {

if (root.right == null) {

root.right = new Node(val);

return root.less_or_equal();

}

return root.less_or_equal() + insert(root.right, val);

}

Posts tagged as “binary indexed tree”

花花酱 Fenwick Tree / Binary Indexed Tree / 树状数组 SP3

C++

Java

Python3

Applications

花花酱 LeetCode 315. Count of Smaller Numbers After Self

Solution 1: Binary Indexed Tree (Fenwick Tree)

C++

Java

Solution 2: BST

C++

Java