# data[].attributes.attachment_link.title
Biblioteca Digital da Produção Intelectual Discente: Sweep line : um paradigma para solução de problemas de geometria computacional

# data[].attributes.attachment_link.description
A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor que autoriza a Biblioteca Digital da Produção Intelectual Discente da Universidade de Brasília (BDM) a disponibilizar o trabalho de conclusão de curso por meio do sítio bdm.unb.br, com as seguintes condições: disponível sob Licença Creative Commons 4.0 International, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante.

# data[].attributes.attachment_link.title
A Constant Optimization of the Binary Indexed Tree Query Operation

# data[].attributes.attachment_link.description
There are several data structures which can calculate the prefix sums of an array efficiently, while handling point updates on the array, such as Segment Trees and Binary Indexed Trees (BIT). Both these data structures can handle the these two operations (query and update) in $O(\log{n})$ time.

# data[].attributes.attachment_link.title
Aplicações Fenwick Tree/Binary Indexed Tree:

# data[].attributes.attachment_link.readable_text
A Binary Indexed (Fenwick) Tree is a data structure that provides efficient methods for implementing dynamic cumulative frequency tables.

This Fenwick Tree data structure uses many bit manipulation techniques. In this visualization, we will refer to this data structure using the term Fenwick Tree (usually abbreviated as 'FT') as the abbreviation 'BIT' of Binary Indexed Tree is usually associated with the usual bit manipulation.

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please .

Suppose that we have a multiset of integers s = {2,4,5,6,5,6,8,6,7,9,7} (not necessarily sorted). There are n = 11 elements in s. Also suppose that the largest integer that we will ever use is m = 10 and we never use integer 0. For example, these integers represent student (integer) scores from [1..10]. Notice that n is independent of m.

We can create a frequency table f from s with a trivial O(n) time loop (recall the first counting pass of counting sort). We can then create cumulative frequency table cf from frequency table f in O(m) time using technique similar to DP 1D prefix sum, e.g., in the table below, cf[5] = cf[4]+f[5] = 2+2 = 4 and afterwards cf[6] = cf[5]+f[6] = 4+3 = 7.

Pro-tip 1: Since you are not , you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

With such cumulative frequency table cf, we can perform Range Sum Query: rsq(i, j) to return the sum of frequencies between index i and j (inclusive), in efficient O(1) time, again using the DP 1D prefix sum (i.e., the inclusion-exclusion principle). For example, rsq(5, 9) = rsq(1, 9) - rsq(1, 4) = 11-2 = 9. As these keys: 5, 6, 7, 8, and 9 represent scores, rsq(5, 9) means the total number of students (9) who scored between 5 to 9, inclusive.

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode ( F11) to enjoy this setup. However, you can use zoom-in ( Ctrl +) or zoom-out ( Ctrl -) to calibrate this.

A dynamic data structure need to support (frequent) updates in between queries. For example, we may update (add) the frequency of score 7 from 2 → 5 (e.g., 3 more students score 7) and update (subtract) the frequency of score 9 from 1 → 0 (e.g., 1 student who previously scored 9 is found to have plagiarized the work and is now penalized to 0, i.e., removed from the scores), thereby updating the table into:

A pure array based data structure for implementing this dynamic cumulative frequency table will need O(m) per update operation. Can we do better?

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/ → to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

Introducing: Fenwick Tree data structure.

There are three mode of usages of Fenwick Tree in this visualization.

The first mode is the default Fenwick Tree that can handle both Point Update (PU) and Range Query (RQ) in O(log n) where n is the largest (integer) index/key in the data structure. Remember that the actual number of keys in the data structure is denoted by another variable m. We abbreviate this default type as PU RQ that simply stands for Point Update Range Query.

This clever arrangement of integer keys idea is the one that originally appears in Peter M. Fenwick's 1994 paper.

You can click the ' Create' menu to create a frequency array f where f[i] denotes the frequency of appearance of key i in our original array of keys s.

IMPORTANT: This frequency array f is not the original array of keys s. For example, if you enter {0,1,0,1,2,3,2,1,1,0}, it means that you are creating 0 one, 1 two, 0 three, 1 four, 2 fives, ..., 0 ten (1-based indexing). The largest index/integer key is m = 10 in this example as in the earlier slides.

If you have the original array s of n elements, e.g., {2,4,5,6,5,6,8,6,7,9,7} from the earlier slides ( s does not need to be necessarily sorted), you can do an O( n) pass to convert s into frequency table f of n indices/integer keys. ( We will provide this alternative input method in the near future).

You can click the ' Randomize' button to generate random frequencies of n keys [1.. n].

Click ' Go' to iteratively call n operations of update(i, f[i]). ( We will provide a faster build FT feature in the near future).

Although conceptually this data structure is a tree, it will be implemented as an integer array called ft that ranges from index 1 to index n (we sacrifice index 0 of our ft array). The values inside the (black outline and white inner) vertices of the Fenwick Tree shown above are the values stored in the 1-based Fenwick Tree ft array.

Currently the edges of this Fenwick Tree are not shown yet. There are two versions of the tree, the interrogation/query tree and the updating Tree.

The values inside the bottom (blue inner) vertices are the values of the frequency array f.

The value stored in index i in array ft (vertex i in the Fenwick Tree), i.e., ft[i] is the cumulative frequency of keys in range [i-LSOne(i)+1 .. i]. Visually, this range is shown by the edges of the (interrogation/query version of) Fenwick Tree.

For a review of LSOne(i) = (i) & -(i) operation, see our bitmask visualization page.

ft[4] = 2 stores the cumulative frequency of keys in [4-LSOne(4)+1 .. 4].
(follow the edge from index 4 back upwards to index 0, plus 1 index).
This is [4-4+1 .. 4] = [1 .. 4] and f[1]+f[2]+f[3]+f[4] = 0+1+0+1 = 2.

ft[6] = 5 stores the cumulative frequency of keys in [6-LSOne(6)+1 .. 6].
(follow the edge from index 6 back upwards to index 4, plus 1 index).
This is [6-2+1 .. 6] = [5 .. 6] and f[5]+f[6] = 2+3 = 5.

The function rsq(j) returns the cumulative frequencies from the first index 1 (ignoring index 0) to index j.

This value is the sum of sub-frequencies stored in array ft with indices related to j via this formula j' = j-LSOne(j). This relationship forms a Fenwick Tree, specifically, the 'interrogation tree' of Fenwick Tree.

We apply this formula iteratively until j is 0.

This function runs is O(log m), regardless of n. Discussion: Why?

We have seen earlier that ft[6] = rsq(5, 6) and ft[4] = rsq(1, 4).
Thus, rsq(6) = ft[6] + ft[6-LSOne(6)] = ft[6] + ft[6-2] =
ft[6] + ft[4] = 5 + 2 = 7.
PS: 4-LSOne(4) = 4-4 = 0.

rsq(i, j) returns the cumulative frequencies from index i to j, inclusive.

If i = 1, we can just use rsq(j) as earlier.
If i > 1, we simply need to return: rsq(j) - rsq(i-1) (Principle of Inclusion-Exclusion).

Discussion: Do you understand the reason?

This function also runs in O(log m), regardless of n. Discussion: Why?

rsq(4, 6) = rsq(6) - [next slide...].
And we have seen earlier that rsq(6) = ft[6]+ft[4] = 5+2 = 7.

rsq(4, 6) = rsq(6) - rsq(3).
We can compute similarly that rsq(3) = ft[3]+ft[2] = 0+1 = 1.

rsq(4, 6) = rsq(6) - rsq(3) = 7 - 1 = 6.

To update the frequency of a key (an index) i by v ( v is either positive or negative; |v| does not necessarily be one), we use update(i, v).

Indices that are related to i via i' = i+LSOne(i) will be updated by v when i < ft.size() (Note that ft.size() is m+1 (as we ignore index 0). These relationships form a variant of Fenwick Tree structure called the 'updating tree'.

Discussion: Do you understand this operation and on why we avoided index 0?

This function also runs in O(log m), regardless of n. Discussion: Why?

The second mode of Fenwick Tree is the one that can handle Range Update (RU) but only able to handle Point Query (PQ) in O(log n).

We abbreviate this type as RU PQ.

Create the data and try running the Range Update or Point Query algorithms on it. Creating the data for this type means inserting several intervals. For example, if you enter [2,4],[3,5], it means that we are updating range 2 to 4 by +1 and then updating range 3 to 5 by +1, thus we have the following frequency table: 0,1,2,2,1 that means 0 one, 1 two, 2 threes, 2 fours, 1 five.

The vertices at the top shows the values stored in the Fenwick Tree (the ft array).

The vertices at the bottom shows the values of the data (the frequency table f).

Notice the clever modification of Fenwick Tree used in this RU PQ type: We increase the start of the range by +1 but decrease one index after the end of the range by -1 to achieve this result.

The third mode of Fenwick Tree is the one that can handle both Range Update (RU) and Range Query (RQ) in O(log n), making this type on par with Segment Tree with Lazy Update that can also do RU RQ in O(log n).

Create the data and try running the Range Update or Range Query algorithms on it.

Creating the data is inserting several intervals, similar as RU PQ version. But this time, you can also do Range Query efficiently.

In Range Update Range Query Fenwick Tree, we need to have two Fenwick Trees. The vertices at the top shows the values of the first Fenwick Tree (BIT1[] array), the vertices at the middle shows the values of the second Fenwick Tree (BIT2[] array), while the vertices at the bottom shows the values of the data (the frequency table). The first Fenwick Tree behaves the same as in RU PQ version. The second Fenwick Tree is used to do clever offset to allow Range Query again.

We have a few more extra stuffs involving this data structure.

Unfortunately, this data structure is not yet available in C++ STL, Java API, Python or OCaml Standard Library as of 2020. Therefore, we have to write our own implementation.

Please look at the following C++/Python/Java/OCaml implementations of this Fenwick Tree data structure in Object-Oriented Programming (OOP) fashion:
fenwicktree_ds.cpp | | |

Again, you are free to customize this custom library implementation to suit your needs.

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

Create - O( m)

RSQ(i, j)

About

Initially conceived in 2011 by Associate Professor Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' - co-authored with Dr. Felix Halim and Dr. Suhendry Effendy - VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

# data[].attributes.attachment_link.keywords[]
binary indexed tree bit fenwick dynamic range sum point update

# data[].attributes.attachment_link.title
Binary Indexed (Fenwick) Tree - VisuAlgo

# data[].attributes.attachment_link.description
A Binary Indexed (Fenwick) Tree is a data structure that provides efficient methods for implementing dynamic cumulative frequency tables.This Fenwick Tree data structure uses many bit manipulation techniques. In this visualization, we will refer to this data structure using the term Fenwick Tree (usually abbreviated as 'FT') as the abbreviation 'BIT' of Binary Indexed Tree is usually associated with the usual bit manipulation.

# data[].attributes.attachment_link.readable_text
For the past few days, I have been reading various explanations of the Binary Indexed Tree. For some reason, none of the explanations were doing it for me. All explanations told me the same thing over and over again. I was not able to find the motive behind this data structure, intuition behind this data structure.

Finally, I decided to sit down, check some examples, diagram them out, check stack overflow and understand it. I now understand the beauty of this data structure, and I think, I can explain it. For those who have gone through this and also for those who don't want to go through this phase, I am writing this post..

Let me tell you one thing, this is going to be a longer post. I will try to cover all the things associated with it. I have included examples for understanding. Give it half an hour, you will surely get new thing to learn.

Wasting no time, lets have a well defined problem.

We will be given an array. And we are asked to answer few queries. Queries will be of two types:- 1) Update X Y : Increment value at Xth index by Y. 2) Sum L R : Print sum of values at index L to R inclusive.

Lets have a look at other approaches in short, before going for BIT (Binary Indexed Tree), so that you will know the need of BIT.

1. We can update any value in the array in single step. So, update operation will need O(1) time. Also, for sum operation, we can traverse the array and find sum. That operation will take O(n) time in worst case.

2. One more thing we can do. At each index, we will store the cumulative frequency i.e. we will store sum of all elements before it including itself. We can construct this new array in O(n). Lets say this array as CF[]. After that, All the sum operation will take O(1) time since we will just subtract CF[L-1] from CF[R] to get the answer for sum L R. But well, we will need to construct CF[] or at least update CF[] every-time update operation is made. The worst case time required for this will be O(n).

Since, the queries are huge in number, we can not always afford O(n) time complexity too. So, here comes the BIT for our rescue.

BINARY INDEXED TREE or FENWICK TREE
CONSTRUCTION of BIT:
Lets have an example with us. Input array is:

[ 5 ] [ 1 ] [ 6 ] [ 4 ] [ 2 ] [ 3 ] [ 3 ] 1 2 3 4 5 6 7

Now, think of what we did in 2nd approach. For each index, we were storing sum of all elements before that element to that index. Right? But because of that, we were needed to change values at all locations for every update.

Now think it this way, what if we store sum of some elements at each index? i.e. Each index will store sum of some elements the number may vary. Similarly, for update operation also, we will need to update only few values, not all. We will see how!

Formally, we will create some benchmarks. Each benchmark will store sum of all elements before that element; but other than those benchmarks, no other point will store sum of all elements, they will store sum of few elements. Okay, if we can do this, what we will need to do to get sum at any point is - intelligently choosing right combination of positions so as to get sum of all elements before that point. And then we will extend it to sum of elements from L to R (for this, the approach will be same as we did in second approach). We will see that afterwards.

Now, having done the base work, lets move ahead.

Before telling HOW will we be doing, I would like to tell you WHAT are we going to do. To remind you, we are going to create BIT[] of given input array.
WHAT:
This is a kind of manual process I am showing.

The benchmarks I was talking about are the powers of 2. Each index, if it is a power of 2, will store the sum of all elements before that. And we will apply this repetitively so as to get what each index will store.

Suppose, we have an array of 16 elements, [1 .. 16].

Powers of 2 are:- 1, 2, 4, 8, 16

These index will store sum of all elements before them.

Fine?

What about others?

Divide this array in two halves:- we get [1..8] and [9 .. 16].

Now think recursively what we did for array of 16, apply same for this, okay?

Seems like little bouncer? Wait, have an example of 8 elements only. Say 8 elements are :

Ok, powers of 2 are: 1 2 4 8 so, in BIT[] indiced 1 2 4 8 will store 1 = 1, 1 + 2 =3, 1 + 2 + .. + 4 = 10 and 1 + 2 + .. + 8 = 36 respectively. Right? Remember, sum of all elements before that element? Right? Good. So, till now, BIT looks like this:-

 [ 1 ] [ 3 ] [ ] [ 10 ] [ ] [ ] [ ] [36] 1 2 3 4 5 6 7 8

Now, divide the given array in 2 halves.

Arr1:

Arr2:

Consider Arr1 first. Powers of 2 are:- 1 2 4 They already have their right values, no need to update.

Now, Consider Arr2: Powers of 2 are: 1 2 4

So, at indices 1, 2 and 4 will store 5 = 5, 5 + 6 = 11, 5 + 6 + 7 + 8 = 26 respectively.

These are the indices according to this new 4-element array. So, actual indices with respect to original array are 4+1, 4+2, 4+4 i.e. 5, 6, 8. We will not care about index 8 as it is already filled in BIT[]. Hence we will update position 5 and 6 now.

BIT will start looking like this now:-

 [ 1 ] [ 3 ] [ ] [ 10 ] [ 5 ] [ 11 ] [ ] [36] 1 2 3 4 5 6 7 8

I think you guys have got what we are doing. Applying same procedure on Arr1 and Arr2, we will get 4 - two element arrays (2 from Arr1 and 2 from Arr2). Follow the same procedure, don't change the value at any index if it is already filled, you get this BIT finally.

 [ 1 ] [ 3 ] [ 3 ] [ 10 ] [ 5 ] [ 11 ] [ 7 ] [36] 1 2 3 4 5 6 7 8

Guys, do take an example of 16 element array and convert it to BIT manually to get the gist.

Now see how will we do this in program.
HOW:
We will continue with our previous example.

Now, start thinking of our array as a binary tree, like this:-

BEFORE: [ 5 ] [ 1 ] [ 6 ] [ 4 ] [ 2 ] [ 3 ] [ 3 ] 1 2 3 4 5 6 7 NOW: 4 [ 4 ] / \ 2 6 [ 1 ] [ 3 ] / \ / \ 1 3 5 7 [5] [6] [2] [3]

Now, we will change value at each node by adding the sum of nodes in its left sub-tree.

UPDATED VERSION: 4 [ 16 ] / \ 2 6 [ 6 ] [ 5 ] / \ / \ 1 3 5 7 [5] [6] [2] [3]

I think you have got what we have just done! Take each node, find sum of all nodes in its left sub-tree and add it to value of that node. And this is what we call is BIT.

BIT: [ 5 ] [ 6 ] [ 6 ] [ 16 ] [ 2 ] [ 5 ] [ 3 ] 1 2 3 4 5 6 7
SUM and UPDATE operations:
Now, we have got the BIT. Lets move ahead and solve our real problem.

Having this tree structure with us, it is to find sum of elements till any index. The idea is to keep a variable ans initialized to 0. Follow the path from root to the index node. Whenever we need to follow a right link, add the value of current node to ans. Once we reach the node, add that value too.

For example, If we want sum of elements upto index 3.

See again,

INPUT ARRAY is: [ 5 ] [ 1 ] [ 6 ] [ 4 ] [ 2 ] [ 3 ] [ 3 ] 1 2 3 4 5 6 7

(so answer should come out as 5 + 1 + 6 = 12)

BIT is: 4 [ 16 ] / \ 2 6 [ 6 ] [ 5 ] / \ / \ 1 3 5 7 [5] [6] [2] [3]

Following the procedure given above.

1> node = root, ans = 0 2> node is 4, index is 3. 3> index < node, go left 4> node = 2, index is 3. 5> index > node, add value(node) to ans and go right i.e. ans = ans + value(node 2) i.e. ans = 0 + 6 i.e. ans = 6 Now, go right 6> node = 3, index = 3 7> node == index, add value of node 3 to ans and return ans i.e. ans = ans + 6 i.e. ans = 12 return 12

In actual implementation, we will be following the reverse path i.e. from node to root.

We will go in actual implementation too. Just have look at update operation as well.

If we want to increment the value at index by say k.

The idea is very similar to sum operation.

Follow the path from root to the index node. Whenever we need to follow a left link, add the value of k to current node. Once we reach the node, add k to that node too. This is because we will need to update the set of nodes in the tree that include that node in its left subtree, so that it will be consistent with our sum operation, right?

I don't think there is any need of example for this case again.

Moving ahead to the implementation.

For this, we will play a bit with BITS -- Binary Numbers. Here comes the fun with bits -- Binary numbers. You will have to do little more work here to figure out the things. I will try my best though.

TREE is: 100 [ 16 ] / \ 010 110 [ 6 ] [ 5 ] / \ / \ 001 011 101 111 [5] [6] [2] [3]

We have just changed the representation of out indices to binary. Ok?

Now, For each index, find the right most SET-bit i.e. '1' and drop the all zeros along with that '1'. We get,

 (--) [ 16 ] / \ 0 1 [ 6 ] [ 5 ] / \ / \ 00 01 10 11 [5] [6] [2] [3]

Here is the thing to be observed. If we treat 0 as LEFT and 1 as RIGHT, each node tells you the path to be followed from root to reach that node. Really? Have example, say node 5, which has 10 there, i.e. RIGHT and LEFT. This is the path we need to follow from root to 5. Cool thing, right?

The reason why this is important to us is, our sum and update operations depends on the this path. Are they not? You remember, Left link, right link, right? During a sum, we just care about the left links we follow. During an update, we just care about the right links we follow. This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key thing behind the efficiency of BIT is:

Given any index n, the next node on the path from root to that index where we go right is directly calculated by RESETing i.e. '0' the last (right most) SET-bit from the binary representation of index. Apply this until we reach the root.

Lets have examples:

TREE is: 4 [ 16 ] / \ 2 6 [ 6 ] [ 5 ] / \ / \ 1 3 5 7 [5] [6] [2] [3]

Say index is 5. The path from 4 to 5 is [ 4 -> RIGHT -> 6 -> LEFT -> 5 ] i.e. we take RIGHT at 4. Binary Representation of 5 is 101. RESET right-most SET-bit. 101 -> 100 4 is the one node from where we will go right STOP here. We have reached the root.

Say index is 7. The path from 4 to 7 is [ 4 -> RIGHT -> 6 -> RIGHT -> 7 ] i.e. we take RIGHT at 4 and 6. Binary Representation of 7 is 111. RESET right-most SET-bit. 111 -> 110 6 is the node from where we will go right RESET right-most SET-bit. 110 -> 100 4 is the node from where we will go right STOP here. We have reached the root.

We will use this information in our implementation.
Implementation:
Now we know, how to go from any index to the root and find what all right-links come in our path.

I will repeat some part of what we have looked.

For SUM: The idea is to keep a variable ans initialized to 0. Follow the path from root to the index node. Whenever we need to follow a right link, add the value of current node to ans. Once we reach the node, add that value too.

For UPDATE: Follow the path from root to the index node. Whenever we need to follow a left link, add the value of k to current node. Once we reach the node, add k to that node too.

Now you have got the complete picture I guess. Everything of What we saw, Why we saw?

For SUM, We need to follow RIGHT-links no matter from root to index or reverse. And we also know how to do that. Right?

So algorithm is:

SUM(index): ans = 0 while(index != 0): ans += BIT[index] index = Reset_Rightmost_SET_bit(index) return ans

Now, the thing remain unanswered is: How to Reset rightmost SETbit? This is a very simple task which I have already covered in my this note. By some observations, we can arrive at a conclusion that, whenever we subtract one from any number say n, the part before a right-most set bit remain same while part after right-most set bit gets inverted. So, just ANDing these can solve our problem.

Reset_Rightmost_SET_bit(n): return n&(n-1)

Please be focused and try to understand this.

We need all left links but we can only know right links with the technique we studied earlier.

We know that, dropping the right-most SET bit and part after that gives us the path from root to node.

So, zeros which come after the right-most one are not useful to us at all.

We will use both these fact and try to find a way.

You must have observed, what happens when we add a 1 to right-most SET bit of a number? [Consider scan from right to left]

1. The first zero from right (which will come after i.e. left to, right-most ONE of number) turns into one

2. Part after (i.e. left to) that ZERO remain unchanged and Part before that get inverted.

Is this not the exact reverse procedure of what used to happen in SUM operation.

This is all what we wanted!

And this is the value i.e. index from which we needed to take the left link to reach to our node from root.

We have successfully found the left link too.

Adding one to right most one is nothing but adding place value of right-most ONE to the number.

Hence our Update operation is as simple as:

UPDATE(index, addition): while(index < length_of_array): BIT[index] += addition index = index + (index & -index)

Try to check the similarity and difference, and you will never forget again.

Here I will stop. I guess you have everything what you need to know about Binary Indexed Tree as a data structure. Now I advice you to implement it yourself and see if you can do it.

You can always refer to the code which I am providing you.

# About using the 2 functions:- # For update, pass index of location to be updated, input array, BIT, value to be added to original number # i.e. new value - original value # For getting sum of elements in range l to r, # Getsum returns sum of elements from beginning to index # Pass index, input array & BIT to function # getsum of l to r = getsum of r - getsum of (l-1) def update(index, a, tree, value): # index is index to be updated, a is input array / list, tree is BIT array, value is value to be added to original # number at index location add = value n = len(a) while index<n: tree[index] += add index = index + (index & (-index)) def getsum(index, a, tree): # index is location upto which you want the sum of elements from beginning # tree is BIT[], a is input array / list n = len(a) ans = 0 while(index>0): ans += tree[index] index = index - (index & (-index)) return ans #Get the user input n = int(raw_input("Number of Elements in array: ")) inputArray = list(map(int, raw_input("Elements in array: ").split())) inputArray.insert(0,0) # insert dummy node to have 1-based indexing #Initialise Binary Indexed Tree to 0's considering that input array is all 0's BIT = [] for i in range(0, n): BIT.append(0) # Now we will construct actual BIT # The 4th parameter is always an additional value which is to be added to element at index location # since we have considered input array as 0 earlier (while initialising BIT), for updating, we will pass actual # value for i in range(1, n): update(i, inputArray, BIT, inputArray[i])

If you like this, Let me know :) Like, Share, Upvote[at the top]!!

Thank you for reading and also thanks for your patience.

P.S.- The same problem can be solved using segment tree data structure as well. I will be covering this in my next post.

HAve look at my other notes here.

# data[].attributes.attachment_link.title
Binary Indexed Tree made Easy - Bhavesh Munot

# data[].attributes.attachment_link.description
For the past few days, I have been reading various explanations of the Binary Indexed Tree. For some reason, none of the explanations were doing it for me. All explanations told me the same thing over and over again. I ...

# data[].attributes.attachment_link.readable_text
Let us consider the following problem to understand Binary Indexed Tree.
We have an array arr[0 . . . n-1]. We would like to
1 Compute the sum of the first i elements.
2 Modify the value of a specified element of the array arr[i] = x where 0 <= i <= n-1.
A simple solution is to run a loop from 0 to i-1 and calculate the sum of the elements. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time. Another simple solution is to create an extra array and store the sum of the first i-th elements at the i-th index in this new array. The sum of a given range can now be calculated in O(1) time, but the update operation takes O(n) time now. This works well if there are a large number of query operations but a very few number of update operations.
Could we perform both the query and update operations in O(log n) time?
One efficient solution is to use Segment Tree that performs both operations in O(Logn) time.
An alternative solution is Binary Indexed Tree, which also achieves O(Logn) time complexity for both operations. Compared with Segment Tree, Binary Indexed Tree requires less space and is easier to implement..
Representation
Binary Indexed Tree is represented as an array. Let the array be BITree[]. Each node of the Binary Indexed Tree stores the sum of some elements of the input array. The size of the Binary Indexed Tree is equal to the size of the input array, denoted as n. In the code below, we use a size of n+1 for ease of implementation.
Construction
We initialize all the values in BITree[] as 0. Then we call update() for all the indexes, the update() operation is discussed below.
Operations

getSum(x): Returns the sum of the sub-array arr[0,...,x]
// Returns the sum of the sub-array arr[0,...,x] using BITree[0..n], which is constructed from arr[0..n-1]
1) Initialize the output sum as 0, the current index as x+1.
2) Do following while the current index is greater than 0.
...a) Add BITree[index] to sum
...b) Go to the parent of BITree[index]. The parent can be obtained by removing
the last set bit from the current index, i.e., index = index - (index & (-index))
3) Return sum.

The diagram above provides an example of how getSum() is working. Here are some important observations.
BITree[0] is a dummy node.
BITree[y] is the parent of BITree[x], if and only if y can be obtained by removing the last set bit from the binary representation of x, that is y = x - (x & (-x)).
The child node BITree[x] of the node BITree[y] stores the sum of the elements between y(inclusive) and x(exclusive): arr[y,...,x).

update(x, val): Updates the Binary Indexed Tree (BIT) by performing arr[index] += val
// Note that the update(x, val) operation will not change arr[]. It only makes changes to BITree[]
1) Initialize the current index as x+1.
2) Do the following while the current index is smaller than or equal to n.
...a) Add the val to BITree[index]
...b) Go to next element of BITree[index]. The next element can be obtained by incrementing the last set bit of the current index, i.e., index = index + (index & (-index))

The update function needs to make sure that all the BITree nodes which contain arr[i] within their ranges being updated. We loop over such nodes in the BITree by repeatedly adding the decimal number corresponding to the last set bit of the current index.
How does Binary Indexed Tree work?
The idea is based on the fact that all positive integers can be represented as the sum of powers of 2. For example 19 can be represented as 16 + 2 + 1. Every node of the BITree stores the sum of n elements where n is a power of 2. For example, in the first diagram above (the diagram for getSum()), the sum of the first 12 elements can be obtained by the sum of the last 4 elements (from 9 to 12) plus the sum of 8 elements (from 1 to 8). The number of set bits in the binary representation of a number n is O(Logn). Therefore, we traverse at-most O(Logn) nodes in both getSum() and update() operations. The time complexity of the construction is O(nLogn) as it calls update() for all n elements.
Implementation:
Following are the implementations of Binary Indexed Tree.

Output
Sum of elements in arr[0..5] is 12
Sum of elements in arr[0..5] after update is 18

Time Complexity: O(NLogN)
Auxiliary Space: O(N)

Can we extend the Binary Indexed Tree to computing the sum of a range in O(Logn) time?
Yes. rangeSum(l, r) = getSum(r) - getSum(l-1).
Applications:
The implementation of the arithmetic coding algorithm. The development of the Binary Indexed Tree was primarily motivated by its application in this case. See this for more details.
Example Problems:
Count inversions in an array | Set 3 (Using BIT)
Two Dimensional Binary Indexed Tree or Fenwick Tree
Counting Triangles in a Rectangular space using BIT

References:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Last Updated : 23 Mar, 2023

# data[].attributes.attachment_link.title
Binary Indexed Tree or Fenwick Tree - GeeksforGeeks

# data[].attributes.attachment_link.description
A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

# data[].attributes.attachment_link.readable_text
Fenwick tree
Binary indexed tree

Type

Bionomal tree

Invented

1989

Invented by

Boris Ryabko

Algorithm

Average

Worst case

Space

O( n)

O( n)

Search

O(log n)

O(log n)

Insert

O(log n)

O(log n)

Delete

O(n)

O(n)

A Fenwick tree or binary indexed tree (BIT) is a data structure that can efficiently update values and calculate prefix sums in an array of values.

This structure was proposed by Boris Ryabko in 1989 with a further modification published in 1992. It has subsequently become known under the name Fenwick tree after Peter Fenwick, who described this structure in his 1994 article.

When compared with a flat array of values, the Fenwick tree achieves a much better balance between two operations: value update and prefix sum calculation. A flat array of values can either store the values or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array values requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both operations to be performed in time. This is achieved by representing the values as a tree with nodes where the value of each node in the tree is the prefix sum of the array from the index of the parent (inclusive) up to the index of the node (exclusive). The tree itself is implicit and can be stored as an array of values, with the implicit root node omitted from the array. The tree structure allows the operations of value retrieval, value update, prefix sum, and range sum to be performed using only node accesses.

Given an array of values, it is sometimes desirable to calculate the running total of values up to each index according to some associative binary operation (addition on integers being by far the most common). Fenwick trees provide a method to query the running total at any index, in addition to allowing changes to the underlying value array and having all further queries reflect those changes.

Fenwick trees are particularly designed to implement the arithmetic coding algorithm, which maintains counts of each symbol produced and needs to convert those to the cumulative probability of a symbol less than a given symbol. Development of operations it supports were primarily motivated by use in that case.

A Fenwick tree is most easily understood by considering a one-based array with values. The corresponding Fenwick tree has nodes with an implicit node 0 at the root. Each level of the tree contains nodes with indices corresponding to sums of distinct powers of 2 (with representing an empty sum 0). For example, level contains nodes and level contains nodes The parent of a given node can be found by clearing the last set bit (LSB) in its index, corresponding to the smallest power of 2 in its sum. For example, the parent of 6 = 110 ₂ is 4 = 100 ₂ .

The below diagram shows the structure of a 16-node Fenwick tree, corresponding to a 15-element array A:

Depiction of a 16-node Fenwick tree containing range sums of a 15-node array A

Let . The value of a node at index corresponds to the range sum of values in , that is, the values of A starting after the parent's index up to the current node's index, inclusive. The values are considered to be the "range of responsibility" for the current node, and consist of (where & denotes bitwise AND) values. Note that the indices in this range do not directly correspond to children of : for example, the range of responsibility for node 2 is but node 1 is not a child of node 2. The root node 0 contains the sum of the empty range with value 0.

The initial process of building the Fenwick tree over an array of values runs in time.

Max/min range query

By keeping track of min/max in following intervals, where index = (k is a odd number), one can find max/min in range :[4]

This means:

One look at all nodes from first node in subtree to this node - follow left childs until one hit a leaf node. If no left child, one does not change position.

One look at all of the nodes, to the right of ones position, of this subtree one are part of - except the root node.

A special case is where the node , that is part of both BIT1 and BIT2, is max/min.

Main idea: If max is in both BIT1 and BIT2, then it must be the root node. Otherwise, its in the left or the right. At some point, one will encounter that max is a leaf node or a root node; by recursevily following this way of thinking.

When building tree; for each value, check if it is in BIT1, BIT2 or both. If it is in BIT1[i], then . Same goes for BIT2. After this, update index to val = val + val & (-val). Repeat until SIZE of array is hit.

When doing range search, one must avoid going into BIT1 and BIT2 that does not contains values within legal range.

The normal max/min query can be implemented in same way as sum/product.

In range sum from [0,r] ,by substracting 2^i = (-val) & val; one go upwards to first left parent, after potentially bypassing all right parents. Then down to a child, with closest index from where one come from. One go downwards to left childs, to the bottom, otherwise. One avoid adding twice; because one always go to the left, never to the right - one only added to the right in add(index,delta)

What is happening, is that one go to closest root of the subtree one are part of; followed by going down to a child, with closest index from where one come from - a node that spans as many values as possible, to the left of our index; in same subtree one are in. It may go through several childs of the root, to cover the subtree. When this subtree is covered, one will try to go to a larger subtree. If one didnt go down to a child, one would have risked going to the right relative to index one are subtracting 2^i = (-val) & val to - which would mean, adding same value twice.

If one didnt go down to the bottom, when one are forced to go to left child first, one would have risked adding same value multiple times.

To find [l,r] range sum, just find sum(0,r) - sum(0,l).

To update the value in a Fenwick tree at index , do following:

Compute the delta .

Then, while index :

Update the index by adding LSB:

Add to the value at node .

When adding a value; one must always go to the right, because if we let the sum always go to left; we avoid risking summing same value twice.

When adding 2^i = -val & val , one simply go to closest parent.

Proceed as follows:

Copy array into array containing tree values

For each index i from 1 to n:

Let . This is the first node larger than that contains in its range of responsibility.

If , update value of node at j:

Since each update happens at most once per index, the resulting algorithm is time complexity. This can also be done in-place in the original array, eliminating the copy and additional storage for .

An analogous operation can be performed to convert a Fenwick tree back into the original frequency array , by iterating backwards from n to 1 and subtracting the value of from the value of at each timestep.

A 2D Fenwick tree (2D BIT) can be constructed as a 1D Fenwick tree where each node of the tree contains a 1D Fenwick tree and stores range sums for submatrices of a 2D matrix A[m,n]. The tree representation remains implicit and the data is stored in an m x n array where position (i, j) in the array corresponds to the jth node of the ith Fenwick tree.

Point update and range query are implemented similarly to the 1D case, but using nested loops (iterating along the column dimension (sub-tree) in the inner loop, and iterating along the row dimension (main tree) in the outer loop).

This idea can be extended to tensors with arbitrary number of dimensions d, with time complexity for range-query and point-update (assuming the tensor is size n along each axis).

A simple pseudocode implementation of the two main operations on a Fenwick tree-query and update-is as following:

function query(tree, index) is sum := 0while index > 0 do sum += tree[index] index -= lso(index)return sumfunction update(tree, index, value) iswhile index < size(tree) do tree[index] += value index += lso(index)

The function computes the least significant 1-⁠bit or last set bit of the given or, equivalently, the largest power of two that is also a divisor of . For example, , as shown in its binary representation: . This function can be simply implemented in code through a bitwise AND operation: lso(n) = n & (-n), assuming a signed integer data type.[3]

One naive algorithm to construct a Fenwick tree consists of initializing the tree with null values and updating each index individually. This solution works in time, but an construction is possible:[6]

function construct(values) is tree := valuesfor every index, value in tree do parentIndex := index + lso(index)if parentIndex < size(tree) then tree[parentIndex] += valuereturn tree

Consider the array

For each entry update such that

, s.t. array[x] <= array[i].

array[x] <= array[i] is guaranteed because i = array[index in list].

A running example:

1. A[array[0]] = A[8] = max (0 <= x < 8) A[x] + 1 = max(0,0,0,...,0) + 1 = 1

2. A[array[1]] = A[5] = max (0 <= x < 5) A[x] + 1 = max(0,0,0,0,...,0) + 1 = 1

3. A[array[2]] = A[7] = max (0 <= x < 7) A[x]+ 1 = max(A[0],[1],A[2],A[3],A[4],A[5],A[6]) + 1 = A[5] + 1 = 1 + 1 = 2

4. A[array[3]] = A[3] = max (0 <= x < 3) A[x] + 1 = max(0,0,0...,0) + 1 = 1

5. A[array[4]] = A[1] = max (0 <= x < 1) A[x] + 1 = max(A[0]) + 1 = 1

6. A[array[5]] = A[2] = max (0 <= x < 2) A[x] + 1 = max(0,1) + 1 = 2

7. A[array[6]] = A[9] = max (0 <= x < 9) A[x] + 1 = max(0,1,2,1,0,1,0,2,1) + 1 = 2+1 = 3

8. A[array[7]] = A[4] = max (0 <= x < 4) A[x] + 1 = max(0,1,2,1) + 1 = 2+1 = 3

9. A[array[8]] = A[6] = max (0 <= x < 6) A[x] + 1 = max(0,1,2,1,3,1) + 1 = 3+1 = 4

That corresponds well to the answer 1,2,4,6

If max value is too large, one can use number compression by using sorting

That is i= indexInSortedList[index in not sorted list], instead of i = array[index in not sorted list]

Take this example:

Array: 166,32,44,66,88

Sorted: 32,44,66,88,166

Then:

A[indexInSortedList[0]] = A[4], and we are back to the problem we are used to

# data[].attributes.attachment_link.description
Fenwick treeBinary indexed tree Type Bionomal tree Invented 1989 Invented by Boris Ryabko Algorithm Average Worst case Space O( n) O( n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(n) O(n) A Fenwick tree or binary indexed tree (BIT) is a data structure that can efficiently update values and calculate prefix sums in an array of values.

# data[].attributes.attachment_caption
Binary Indexed Tree or Fenwick Tree | Construction and Operations | GeeksforGeeks

# data[].attributes.attachment_link.title
Binary Indexed Tree or Fenwick Tree | Construction and Operations | GeeksforGeeks