Stack Overflow
Stack Overflow

Questions tagged [fenwick-tree]

A Fenwick tree (or binary indexed tree) is a fast data structure for storing and maintaining cumulative frequency tables.

75 questions
66
votes
3 answers

What does (number & -number) mean in bit programming?

For example: int get(int i) { int res = 0; while (i) { res = (res + tree[i]) % MOD; i -= ( (i) & (-i) ); } return res; } A tree update function: void update(int i, int val) { while (i <= m) { tree[i] =…
SwadhIn
  • 717
  • 1
  • 9
  • 19
34
votes
2 answers

Is it possible to build a Fenwick tree in O(n)?

Fenwick tree is a data structure which allows two kind of operations (you can augment it with more operations): point update update(index, value) prefix sum query(index) Both of the operations are in O(log(n)) where n is the size of an array. I…
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
30
votes
4 answers

Fenwick tree vs Segment tree

I needed to compute sums within a range on an array, so I came across Segment Tree and Fenwick Tree and I noticed that both of these trees query and update with the same asymptotic running time. I did a bit more research, and these 2 data structures…
Will Kanga
  • 652
  • 1
  • 6
  • 12
23
votes
5 answers

Is it possible to query number of distinct integers in a range in O(lg N)?

I have read through some tutorials about two common data structure which can achieve range update and query in O(lg N): Segment tree and Binary Indexed Tree (BIT / Fenwick Tree). Most of the examples I have found is about some associative and…
shole
  • 4,046
  • 2
  • 29
  • 69
23
votes
2 answers

How to adapt Fenwick tree to answer range minimum queries

Fenwick tree is a data-structure that gives an efficient way to answer to main queries: add an element to a particular index of an array update(index, value) find sum of elements from 1 to N find(n) both operations are done in O(log(n)) time and I…
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
19
votes
3 answers

Solving Range Minimum Queries using Binary Indexed Trees (Fenwick Trees)

Formally, the Range Minimum Query Problem is: Given an array A[0, N-1] , Find the position of the element with the minimum value between any two given indices. Now, the standard solution is to use a segment tree and has been described here.…
Ankesh Anand
  • 1,695
  • 2
  • 16
  • 24
12
votes
1 answer

What does `(i & (i + 1)) - 1` mean? (in Fenwick Trees)

While learning about Fenwick Trees, I found this implementation: Source: https://algorithmist.com/wiki/Fenwick_tree class Fenwick_Tree_Sum { vector tree; Fenwick_Tree_Sum(const vector& Arg)//Arg is our array on which we are going…
StackExchange123
  • 1,871
  • 9
  • 24
12
votes
3 answers

Need a clear explanation of Range updates and range queries Binary indexed tree

I have gone through few tutorials of Range update - Range queries of Binary indexed tree. I'm unable to understand any of them. I don't understand the need of building another tree. Could someone explain it to me in plain English with an example?
user3739818
  • 241
  • 1
  • 3
  • 11
12
votes
1 answer

Increment Range using Fenwick Tree

I was wondering if a Fenwick Tree (or Binary Indexed Tree) can be modified to: 1) Increment the frequency all elements in a range by a certain amount 2) Query the frequency of a single element. This is as opposed to the traditional Fenwick Tree…
Peter
  • 415
  • 7
  • 13
11
votes
2 answers

Are interval, segment, fenwick trees the same?

Today i listened a lecture about fenwick trees (binary indexed trees) and the teacher says than this tree is a generalization of interval and segment trees, but my implementations of this three data structures are different. Is this afirmation true?…
Luiguis
  • 404
  • 1
  • 5
  • 11
10
votes
2 answers

How to do a range update in Binary Indexed Tree or Fenwick Tree?

I am trying to solve this problem in UVA with Binary Indexed Tree: Problem H Ahoy, Pirates! Input: Standard Input Output: Standard Output In the ancient pirate ages, the Pirate Land was divided into two teams of pirates, namely, the Buccaneer…
Tamim Addari
  • 7,591
  • 9
  • 40
  • 59
9
votes
4 answers

How to efficiently find a contiguous range of used/free slots from a Fenwick tree

Assume, that I am tracking the usage of slots in a Fenwick tree. As an example, lets consider tracking 32 slots, leading to a Fenwick tree layout as shown in the image below, where the numbers in the grid indicate the index in the underlying array…
Alex
  • 13,024
  • 33
  • 62
7
votes
1 answer

Range Query the number of inversion in O(lg N)

Given an unsorted array of n integers, I know I can find the total number of inversions using BIT in O(N lg N)following this method: Count Inversion by BIT However is it possible if I have to query an arbitrary range for the total # of inversions in…
shole
  • 4,046
  • 2
  • 29
  • 69
7
votes
1 answer

3d Fenwick tree

I have a three-dimensional fenwick tree data structure. I need to calculate sum on some segment from (x0, y0, z0) to (x, y, z) What is the formula for inclusion-exclusion? For instance, for 2D variant it is s = sum(x, y) - sum(x, y0 - 1) - sum(x0 -…
Denys Astanin
  • 71
  • 1
  • 3
6
votes
1 answer

Number of Increasing Subsequences of length k

I am trying to understand the algorithm that gives me the number of increasing subsequences of length K in an array in time O(nklog(n)). I know how to solve this very same problem using the O(k*n^2) algorithm. I have looked up and found out this…
Andrés
  • 841
  • 2
  • 13
  • 31
1
2 3 4 5