Fenwick Tree

Fenwick Tree, also known as Binary Indexed Tree (BIT), provides an efficient way to compute prefix sum on an array allowing array modification. Consider an array A of size N. We need to perform two kinds of operations on this array:
1. Modify array element at index i
2. Compute prefix sum up to index i One efficient solution is to use segment tree that can perform both operations in O(logn) time. But then why learn Fenwick Tree data structure when we already have a solution. It is because Binary Indexed Trees require less space and are very easy to implement.

Find Value After N Operations to Remove N Characters of String S with Given Constraints

By Malay Gain

● Published At Jan 2022

In this article, we will learn how to find value after N operations to remove N characters of string S with given constraints.... Keep reading ..

Sum of previous numbers that are greater than current number for given array

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently.... Keep reading ..

Finding XOR of the Array Elements in a Given Range with Updates using Fenwick Tree

By GAZAL ARORA

● Published At Mar 2022

In this article, we will design an algorithm to solve the queries of finding the XOR of array elements in a given range with updates of array values using the Fenwick Tree.
... Keep reading ..

Queries for the Number of Nodes having Values Less than V in the Subtree of a Node

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Count smaller elements on right side and greater elements on left side using Binary Index Tree

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Find the Number of Pair of Ideal Nodes in a Given Tree

By Riya

● Published At Feb 2022

This article will discuss the problem "Find the number of pair of ideal nodes in a given tree", an approach to solve this problem, its C++ implementation, and time and space complexity.... Keep reading ..

Range Sum Queries and Update with Square Root

By Soumya Agrawal

● Published At Mar 2022

This article will cover the approach and implementation of the problem- Range Sum Queries and Update with Square Root.... Keep reading ..

Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries)

By Jaglike Makkar

● Published At Feb 2022

This article will discuss finding the number of elements greater than K from index L to R for offline queries using the Fenwick Tree. We will also focus on the complexity of our solution.... Keep reading ..

Count of Inversion of size K in a given array

By Riya

● Published At Feb 2022

This article will discuss the problem "Count of Inversions of size K in a given array," an approach to solve this problem, its C++ implementation, and time and space complexity.... Keep reading ..

XOR of Numbers that Appeared Even Number of Times in Given Range

By Anant Dhakad

● Published At Jan 2022

In this article, we will take a coding problem based on the application of the Fenwick Tree, also known as the Binary Indexed Tree. Fenwick trees are used to calculate prefix sum efficiently and handle updates efficiently. ... Keep reading ..

Sum of Interval and Update with Number of Divisors

By Jaglike Makkar

● Published At Feb 2022

In this article, we will discuss the approach to find the sum of a segment of an array and update a segment by replacing every number with its number of divisors for multiple queries. We will also focus on the complexity of our approach.... Keep reading ..

Maximum Sum of Increasing Subsequence using Fenwick Tree

By Apoorv

● Published At Feb 2022

This article will discuss the solution for finding the Maximum Sum of Increasing Subsequence using Fenwick Tree along with the solution; the article focuses on the time and space complexity of the solution.... Keep reading ..

Queries for Number of Distinct Elements in the Subarray

By Jaglike Makkar

● Published At Feb 2022

In this article, we will discuss the approach to finding the number of distinct elements in the subarray for multiple queries. We will also focus on the complexity of our approach.... Keep reading ..

Number of Elements less than or equal to a given number in a given subarray

By Riya

● Published At Feb 2022

This article will discuss the problem "Find the number of elements less than or equal to a given number in a given subarray, its C++ implementation, and time and space complexity.... Keep reading ..

Count Inversions using Fenwick Tree

By SHIKHAR SONI

● Published At Jan 2022

The article covers the use of the Fenwick tree to determine the inversion count in an array... Keep reading ..

Two Dimensional Fenwick Tree

By Apoorv

● Published At Feb 2022

This article will discuss the Two Dimensional Fenwick Tree concept and its application and its space and time complexity.... Keep reading ..

Binary Indexed Tree or Fenwick Tree

By Malay Gain

● Published At Nov 2021

In this article, we will learn Binary Indexed Tree or Fenwick Tree.
... Keep reading ..

Binary Indexed Tree or Fenwick Tree

By Abhishek Ranjan

● Published At Jan 2022

In this article, we will discuss Binary Index Tree/Fenwick Tree and see its implementation in c++.... Keep reading ..

Range Update and Range Queries in Binary Indexed Tree

By Riya

● Published At Mar 2022

This article will discuss "Range update and Range Queries in Binary Indexed Tree," its C++ implementation, and time and space complexity.... Keep reading ..

Binary Indexed Tree: Range Update and Range Queries

By Shreya Deep

● Published At Jan 2022

This article describes the methods to do range update and range queries on a binary indexed tree... Keep reading ..

Querying the Number of Distinct Colors in a Subtree of a Colored Tree using BIT

By Abhishek Ranjan

● Published At Jan 2022

This article will solve a problem on trees using the binary index tree/Fenwick tree. Through this article, we will learn an algorithm to flatten the given tree and see an application of the binary index tree.... Keep reading ..

Minimum Possible Integer After at Most K Adjacent Swaps On Digits

By Ujjawal Gupta

● Published At Mar 2022

In this blog, we will discuss an interesting interview problem, namely the minimum possible integer after at most K adjacent swaps on digits. It is a Leetcode Hard problem.... Keep reading ..

The Skyline Problem

By Rhythm Jain

● Published At Nov 2021

This article discusses The Skyline Problem, which is one of the most challenging questions asked in interviews of tech giants. ... Keep reading ..