Stack Overflow
Stack Overflow

Questions tagged [binary-indexed-tree]

Binary Indexed Tree(BIT) also known as Fenwick Tree is a tree based advanced data structure that can be used to store and calculate cumulative sum or frequency. BIT is more efficient than other data structures (like Segment Tree and other RMQ) considering the time complexity, memory complexity and Line of Code.

Binary Indexed Tree(BIT) also known as Fenwick Tree is a data structure providing efficient methods for calculation and manipulation of the prefix sums of a table of values. It was proposed by Peter Fenwick in 1994.

BIT primarily solve the problem of balancing prefix sum calculation efficiency with element modification efficiency. The efficiency of these operations comes as a trade-off - greater efficiency in prefix sum calculation is achieved by pre-calculating values, but as more values are pre-calculated more must be re-calculated upon any modification to the underlying value table.

The initial building of BIT requires O(nLogn) time. But it can effectively run a range query on the built tree in O(logn) time and also update the tree in O(logn) time. Most importantly BIT can store the frequency table or the build tree in O(n) memory space.

Use this tag when you are asking a problem related to Binary Indexed Tree. You should include code snippet or pseudo-code if necessary.

Referance

  1. Fenwick Tree, Wikipedia
  2. Topcoder Tutorial
  3. A New Data Structure for Cumulative Frequency Tables (1994)
28 questions
6
votes
4 answers

What does "x += x & (-x)" mean?

I found that many people use x += x & (-x), x -= x & (-x) to solve the interval tree problem (While implementing data structures like segment tree, binary indexed tree etc). Can you explain what that equation means? For Example: void update(int m,…
eleven22
  • 83
  • 2
  • 7
6
votes
1 answer

How to find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)

How can I find the total number of Increasing sub-sequences of certain length with Binary Index Tree(BIT)? Actually this is a problem from Spoj Online Judge Example Suppose I have an array 1,2,2,10 The increasing sub-sequences of length 3 are 1,2,4…
Mostafiz Rahman
  • 8,169
  • 7
  • 57
  • 74
3
votes
0 answers

How can we calculate weighted cumulative sum of squares with prefix range updates by one?

Given an array A with n elements which starts with all 0s and another array W also with n elements (all greater than 0), we want to perform the following operation repeatedly; For a given k, increment A[0], A[1], .... A[k] each by 1, and report the…
piedpiper
  • 1,222
  • 3
  • 14
  • 27
3
votes
1 answer

Update step in Fenwick Trees

My question concerns the full reasoning behind the update step in Binary Indexed Trees (Fenwick Trees). As such, when updating our array with a certain increment, at a certain position, the update goes like this: void updateBIT(int BITree[], int n,…
user43389
  • 721
  • 6
  • 18
3
votes
0 answers

Difference between Binary Search Tree and Binary Index Tree

Is Binary Index Tree and Binary Search Tree are same thing? If not whats the actual difference between them and when to use what?
0xAliHn
  • 18,390
  • 23
  • 91
  • 111
2
votes
0 answers

Binary Indexed Tree: Why does "i + lowBit(i)" work?

I know that if we want to update node with index i, we need to recursively update node i = i + lowBit(i) until the new value exceeds the size of the binary indexed tree. My question is: how to prove that i + lowBit(i) can cover all the nodes we…
ihainan
  • 65
  • 7
2
votes
0 answers

How to solve problems with Binary Indexed Tree?

This question sounds very vague and needs some explanation: I learned about Binary Indexed Tree a few weeks ago. This data structure is a brilliant design. It actually took me very long to figure out how it's built thanks to this video (I mean...…
xialin
  • 7,686
  • 9
  • 35
  • 66
2
votes
1 answer

Brackets matching using BIT

edit: I was trying to solve a spoj problem. Here is the link to the problem : http://spoj.pl/problems/BRCKTS I can think of two possible data structures for solving the problem one using segment tree and the other using a BIT. I have already…
amitkarmakar
  • 1,223
  • 2
  • 13
  • 23
1
vote
1 answer

Quick Way of Finding How many Substrings has first and last character repeated inside

This is a problem about substrings that I created. I am wondering how to implement an O(nlog(n)) solution to this problem because the naive approach is pretty easy. Here is how it goes. You have a string S. S has many substrings. In some substrings,…
halcyon44
  • 13
  • 4
1
vote
2 answers

Count "minimal" values

Problem: I have an input of n vectors: (x, y, z): x ∈ {1..n},y ∈ {1..n},z ∈ {1..n} (every "dimension" is set(1..n)) *I mean that in one vector x,y,z can be the same(x=y=z), but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2 v1>v2 if and only if…
bordus
  • 35
  • 7
1
vote
1 answer

Answer queries about the number of distinct numbers in a given range

The problem I have an array with N numbers. The numbers may be disctints and may also be unordered. I have to answer Q queries about how many distinct numbers there are between A and B. Where A, B are indices between 0 <= A <= B < array.Length. I…
Diego Becquer
  • 81
  • 6
1
vote
0 answers

how to get inversion count with update

Inversion count in an given array is a very famous with a time complexity of O(NlogN). However, I wonder whether there is a way to do it with update. Input format: first line consist of an integer n; second line includes n integer which is the…
Brian Lee
  • 51
  • 7
1
vote
1 answer

Application of binary indexed tree

I was trying to solve this algorithmic problem and I came across this nice solution: "The idea is to treat the ai, bi and ci asymmetrically. The BIT supports minimum queries for key intervals starting at 1. We use ci as values and bi as keys.…
aroma
  • 1,370
  • 1
  • 15
  • 30
1
vote
1 answer

range XORed sum using BIT or Fenwick tree

For a given array of integers, we have to calculate XORed sum withing a given range [L, R], by XORed sum I mean Σ(Arr[i]^p) where i:[L,R] and p is some number. This can be easily done while calculating the XORed sum till every i-th element in array…
Roshan
  • 150
  • 16
1
vote
2 answers

Can someone please explain the solution to "Almost sorted intervals" to me?

Here is the problem, and here is a solution. First part is simple enough. It's the second part that I don't get, no matter how hard I try. You basically have two sets of intervals and need to find all intersections where one interval is not…
thule
  • 4,034
  • 21
  • 31
1
2