LinkedHashMap will not be the fastest answer for this question because the input characters are just from 'a' to 'z', but in other situations it might be faster than two pass solutions. I post this just for inspiration.
public int firstUniqChar(String s) {
Map<Character, Integer> map = new LinkedHashMap<>();
Set<Character> set = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (set.contains(s.charAt(i))) {
if (map.get(s.charAt(i)) != null) {
map.remove(s.charAt(i));
}
} else {
map.put(s.charAt(i), i);
set.add(s.charAt(i));
}
}
return map.size() == 0 ? -1 : map.entrySet().iterator().next().getValue();
}
My solution is pretty straightforward. It takes O(n) and goes through the string twice:
Get the frequency of each character.
Get the first character that has a frequency of one.
Actually the code below passes all the cases. However, according to @xietao0221, we could change the size of the frequency array to 256 to store other kinds of characters. Thanks for all the other comments and suggestions. Fight on!
public int firstUniqChar(String s) {
int freq [] = new int[26];
for(int i = 0; i < s.length(); i ++)
freq [s.charAt(i) - 'a'] ++;
for(int i = 0; i < s.length(); i ++)
if(freq [s.charAt(i) - 'a'] == 1)
return i;
return -1;
}
The idea is to use a slow pointer to point to the current unique character and a fast pointer to scan the string. The fast pointer not only just add the count of the character. Meanwhile, when fast pointer finds the identical character of the character at the current slow pointer, we move the slow pointer to the next unique character or not visitedcharacter. (20 ms)
Is the time complexity O(n^2) ?
publicclassSolution {
publicint firstUniqChar(String s) {
if (s==null || s.length()==0) return-1;
int len = s.length();
if (len==1) return0;
char[] cc = s.toCharArray();
int slow =0, fast=1;
int[] count = new int[256];
count[cc[slow]]++;
while (fast < len) {
count[cc[fast]]++;
// if slow pointer is not a unique character anymore, move to the next unique onewhile (slow < len && count[cc[slow]] > 1) slow++;
if (slow >= len) return-1; // no unique character existif (count[cc[slow]]==0) { // not yet visited by the fast pointer
count[cc[slow]]++;
fast=slow; // reset the fast pointer
}
fast++;
}
return slow;
}
We can build this heap by putting our data items into the array in any order and then ``heapifying'' the array. Examine the first non-leaf node in the heap-array and compare its key value against that of its greatest child. If it is greater than its greater children, proceed to the next non-leaf node and repeat this process. However, if it is not greater than its greater children then swap these elements. Before continuing to the next non-leaf node and repeating the process the algorithm must be certain that the newly demoted value is in the correct spot. Thus the process must recurse on this demoted value before it can continue with the next leaf on its way to the root. By moving up the whole heap-array in this manner all nodes will end up being greater than their children.
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
What is the worst case time complexity of the above algo? Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n). See following links for the proof of time complexity.
void correctNodeIndexByShifting(int arrayIndex) { int changingArrayIndex = arrayIndex; if ((changingArrayIndex < 0) || (changingArrayIndex >= this.numberOfNodes)) { throw new IllegalArgumentException( "In method shiftDown of class " + "MaxHeap the value: " + changingArrayIndex + " represents a node that does not exist in the current heap"); } while (!this.isLeafNode(changingArrayIndex)) { int childIndex = this.getLeftChildIndex(changingArrayIndex); if ((childIndex < (this.numberOfNodes - 1)) && (this.heap[childIndex] .compareTo(this.heap[childIndex + 1]) < 0)) { childIndex++; // childIndex is not at index of child with // greater node value } if (this.heap[changingArrayIndex].compareTo(this.heap[childIndex]) >= 0) { return; } this.swap(changingArrayIndex, childIndex); changingArrayIndex = childIndex; // node shifted down }
}
public void insert(E nodeValue) { if (this.capacity <= this.numberOfNodes) { throw new IllegalArgumentException("In method insert of class " + "MaxHeap the element: " + nodeValue + " could not be inserted because the max-heap is full"); }
int currentNodePosition = this.numberOfNodes++; this.heap[currentNodePosition] = nodeValue;
// start at the end of most bottom right leaf node and shift up // until the nodeValue has a parent with a greater or equal value while ((currentNodePosition != 0) && (this.heap[currentNodePosition].compareTo(this.heap[this .getParentIndex(currentNodePosition)]) > 0)) { this.swap(currentNodePosition, this.getParentIndex(currentNodePosition)); currentNodePosition = this.getParentIndex(currentNodePosition); }
}
public E remove(int arrayIndex) { int changingArrayIndex = arrayIndex; if ((changingArrayIndex < 0) || (changingArrayIndex >= this.numberOfNodes)) { throw new IllegalArgumentException("In method remove of class " + "MaxHeap the input node postion to be removed is invalid"); }
// if the most bottom right node is being removed there is no work to be // done if (changingArrayIndex == (this.numberOfNodes - 1)) { this.numberOfNodes--; } else { // swap node to be removed with most bottom right node this.swap(changingArrayIndex, --this.numberOfNodes);
// if swapped node is large, shift it up the tree while ((changingArrayIndex > 0) && (this.heap[changingArrayIndex].compareTo(this.heap[this .getParentIndex(changingArrayIndex)]) > 0)) { this.swap(changingArrayIndex, this.getParentIndex(changingArrayIndex)); changingArrayIndex = this.getParentIndex(changingArrayIndex); } if (this.numberOfNodes != 0) { // if swapped node is small, shift it down the tree this.correctNodeIndexByShifting(changingArrayIndex); } } return this.heap[changingArrayIndex];
} http://analgorithmaday.blogspot.com/2011/01/build-max-heap-with-input-array.html
Using binary Indexed tree also, we can perform both the tasks in O(logN) time. But then why to learn another data structure when segment tree can do the work for us. It’s because binary indexed trees require less space and are very easy to implement during programming contests (the total code is not more than 8-10 lines).
x & (-x) gives the last set bit in a number . How?
Say (in binary) is the number whose last set bit we want to isolate.
Here is some binary sequence of any length of 1’s and 0’s and is some sequence of any length but of 0’s only. Remember we said we want the LAST set bit, so for that tiny intermediate 1 bit sitting between a and b to be the last set bit, b should be a sequence of 0’s only of length zero or more.
The last set bit is given by x&(-x) = (10)1(0) & (01)1(0) = 0010 = 2 (in decimal)
We know the fact that each integer can be represented as the sum of powers of two. Similarly, for a given array of size , we can maintain an array such that, at any index we can store the sum of some numbers of the given array. This can also be called a partial sum tree.
Let’s use an example to understand how stores partial sums.
//for ease, we make sure our given array is 1-based indexedint a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
The above picture shows the binary indexed tree, each enclosed box of which denotes the value and each stores partial sum of some numbers.
Notice
{ a[x],if x is odd
BIT[x]= a[1]+...+ a[x],if x is power of 2}
To generalize this every index in the array stores the cumulative sum from the index to (both inclusive), where represents the last set bit in the index .
Sum of first 12 numbers in array
Similarly, sum of first 6 elements
Sum of first 8 elements
Let’s see how to construct this tree and then we will come back to querying the tree for prefix sums. is an array of size = 1 + the size of the given array on which we need to perform operations. Initially all values in are equal to . Then we call update() operation for each element of given array to construct the Binary Indexed Tree. The update() operation is discussed below.
void update(int x,int val)//add "val" at index "x"{for(; x <= n; x += x&-x)
BIT[x]+= val;}
Suppose we call update(13, 2).
Here we see from the above figure that indices 13, 14, 16 cover index 13 and thus we need to add 2 to them also.
Initially is 13, we update
BIT[13]+=2;
Now isolate the last set bit of and add that to , i.e. x += x&(-x)
Last bit is of is which we add to , then , we update
BIT[14]+=2;
Now is , isolate last bit and add to , becomes , we update
BIT[16]+=2;
In this way, when an update() operation is performed on index we update all the indices of which cover index and maintain the .
If we look at the for loop in update() operation, we can see that the loop runs at most the number of bits in index which is restricted to be less or equal to (the size of the given array), so we can say that the update operation takes at most time.
How to query such structure for prefix sums? Let’s look at the query operation.
int query(int x)//returns the sum of first x elements in given array a[]{int sum =0;for(; x >0; x -= x&-x)
sum += BIT[x];return sum;}
The above function query() returns the sum of first elements in given array. Let’s see how it works.
Suppose we call query(14), initially sum = 0 is we add to our sum variable, thus
Now we isolate the last set bit from and subtract it from Last set bit in , thus
We add to our sum variable, thus
Again we isolate last set bit from and subtract it from Last set bit in is , thus
We add to our sum variable, thus
Once again we isolate last set bit from and subtract it from Last set bit in is , thus
Since , the for loop breaks and we return the prefix sum.
Talking about time complexity, again we can see that the loop iterates at most the number of bits in which will be at most (the size of the given array). Thus, the *query operation takes time
Before going for Binary Indexed tree to perform operations over range, one must confirm that the operation or the function is:
Associative. i.e this is true even for seg-tree
Has an inverse. eg:
Addition has inverse subtraction (this example we have discussed)
Multiplication has inverse division
has no inverse, so we can’t use BIT to calculate range gcd’s
Sum of matrices has inverse
Product of matrices would have inverse if it is given that matrices are degenerate i.e. determinant of any matrix is not equal to 0
Space Complexity: for declaring another array of size
Time Complexity: for each operation(update and query as well)
Applications:
Binary Indexed trees are used to implement the arithmetic coding algorithm. Development of operations it supports were primarily motivated by use in that case.
Binary Indexed Tree can be used to count inversions in an array in time.
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).
// Max tree size
finalstaticintMAX = 1000;
staticintBITree[] = newint[MAX];
/* n --> No. of elements present in input array.
BITree[0..n] --> Array that represents Binary
Indexed Tree.
arr[0..n-1] --> Input array for whic prefix sum
is evaluated. */
// Returns sum of arr[0..index]. This function
// assumes that the array is preprocessed and
// partial sums of array elements are stored
// in BITree[].
intgetSum(intindex)
{
intsum = 0; // Iniialize result
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse ancestors of BITree[index]
while(index>0)
{
// Add current element of BITree
// to sum
sum += BITree[index];
// Move index to parent node in
// getSum View
index -= index & (-index);
}
returnsum;
}
// Updates a node in Binary Index Tree (BITree)
// at given index in BITree. The given value
// 'val' is added to BITree[i] and all of
// its ancestors in tree.
publicstaticvoidupdateBIT(intn, intindex,
intval)
{
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse all ancestors and add 'val'
while(index <= n)
{
// Add 'val' to current node of BIT Tree
BITree[index] += val;
// Update index to that of parent
// in update View
index += index & (-index);
}
}
/* Function to construct fenwick tree
from given array.*/
voidconstructBITree(intarr[], intn)
{
// Initialize BITree[] as 0
for(inti=1; i<=n; i++)
BITree[i] = 0;
// Store the actual values in BITree[]
// using update()
for(inti = 0; i < n; i++)
updateBIT(n, i, arr[i]);
}
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).
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.
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.
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).
Lets have an example with us. Input array is:
[5][1][6][4][2][3][3]1234567
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.
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 :
12345678
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]12345678
Now, divide the given array in 2 halves.
Arr1:
1234
Arr2:
5678
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]12345678
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.
One approach to get the frequency at a given index is to maintain an additional array. In this array, we separately store the frequency for each index. Reading or updating a frequency takes O(1) time; the memory space is linear. However, it is also possible to obtain the actual frequency at a given index without using additional structures.
First, the frequency at index idx can be calculated by calling the function read twice – f[idx] = read(idx) – read(idx – 1) — by taking the difference of two adjacent cumulative frequencies. This procedure works in 2 * O(log n) time. There is a different approach that has lower running time complexity than invoking read twice, lower by a constant factor. We now describe this approach.
The main idea behind this approach is motivated by the following observation. Assume that we want to compute the sum of frequencies between two indices. For each of the two indices, consider the path from the index to the root. These two paths meet at some index (at latest at index 0), after which point they overlap. Then, we can calculate the sum of the frequencies along each of those two paths until they meet and subtract those two sums. In that way we obtain the sum of the frequencies between that two indices.
We translate this observation to an algorithm as follows. Let x be an index and y=x-1. We can represent (in binary notation) y as a0b, where bconsists of all ones. Then, x is a1b¯ (note that b¯ consists of all zeros). Now, consider the first iteration of the algorithm read applied to x. In the first iteration, the algorithm removes the last bit of x, hence replacing x by z=a0b¯.
Now, let us consider how the active index idx of the function read changes from iteration to iteration on the input y. The function read removes, one by one, the last bits of idx. After several steps, the active index idx becomes a0b¯ (as a reminder, originally idx was equal to y=a0b), that is the same as z. At that point we stop as the two paths, one originating from x and the other one originating from y, have met. Now, we can write our algorithm that resembles this discussion. (Note that we have to take special care in case x equals 0.) A function in C++:
int readSingle(int idx){
int sum = tree[idx]; // this sum will be decreased
if (idx > 0){ // the special case
int z = idx - (idx & -idx);
idx--; // idx is not important anymore, so instead y, you can use idx
while (idx != z){ // at some iteration idx (y) will become z
sum -= tree[idx];
// substruct tree frequency which is between y and "the same path"
idx -= (idx & -idx);
}
}
return sum;
}
Scaling the entire tree by a constant factor
Now we describe how to scale all the frequencies by a factor c. Simply, each index idx is updated by -(c – 1) * readSingle(idx) / c (because f[idx] – (c – 1) * f[idx] / c = f[idx] / c). The corresponding function in C++ is:
void scale(int c){
for (int i = 1 ; i <= MaxIdx ; i++)
update(-(c - 1) * readSingle(i) / c , i);
}
This can also be done more efficiently. Namely, each tree frequency is a linear composition of some frequencies. If we scale each frequency by some factor, we also scale a tree frequency by that same factor. Hence, instead of using the procedure above, which has time complexity O(MaxIdx * log MaxIdx), we can achieve time complexity of O(MaxIdx) by the following:
void scale(int c){
for (int i = 1 ; i <= MaxIdx ; i++)
tree[i] = tree[i] / c;
}
Time complexity: O(MaxIdx).
Find index with given cumulative frequency
Consider a task of finding an index which corresponds to a given cumulative frequency, i.e., the task of perfoming an inverse operation of read. A naive and simple way to solve this task is to iterate through all the indices, calculate their cumulative frequencies, and output an index (if any) whose cumulative frequency equals the given value. In case of negative frequencies it is the only known solution. However, if we are dealing only with non-negative frequencies (that means cumulative frequencies for greater indices are not smaller) we can use an algorithm that runs in a logarithmic time, that is a modification of binary search. The algorithms works as follows. Iterate through all the bits (starting from the highest one), define the corresponding index, compare the cumulative frequency of the current index and given value and, according to the outcome, take the lower or higher half of the interval (just like in binary search). The corresponding function in C++ follows:
// If in the tree exists more than one index with the same
// cumulative frequency, this procedure will return
// some of them
// bitMask - initialy, it is the greatest bit of MaxIdx
// bitMask stores the current interval that should be searched
int find(int cumFre){
int idx = 0; // this variable will be the output
while (bitMask != 0){
int tIdx = idx + bitMask; // the midpoint of the current interval
bitMask >>= 1; // halve the current interval
if (tIdx > MaxIdx) // avoid overflow
continue;
if (cumFre == tree[tIdx]) // if it is equal, simply return tIdx
return tIdx;
else if (cumFre > tree[tIdx]){
// if the tree frequency "can fit" into cumFre,
// then include it
idx = tIdx; // update index
cumFre -= tree[tIdx]; // update the frequency for the next iteration
}
}
if (cumFre != 0) // maybe the given cumulative frequency doesn't exist
return -1;
else
return idx;
}
// If in the tree exists more than one index with a same
// cumulative frequency, this procedure will return
// the greatest one
int findG(int cumFre){
int idx = 0;
while (bitMask != 0){
int tIdx = idx + bitMask;
bitMask >>= 1;
if (tIdx > MaxIdx)
continue;
if (cumFre >= tree[tIdx]){
// if the current cumulative frequency is equal to cumFre,
// we are still looking for a higher index (if exists)
idx = tIdx;
cumFre -= tree[tIdx];
}
}
if (cumFre != 0)
return -1;
else
return idx;
}
Example for cumulative frequency 21 and function find:
First iteration - tIdx is 16; tree[16] is greater than 21; halve bitMask and continue
Second iteration - tIdx is 8; tree[8] is less than 21, so we should include first 8 indices in result, remember idx because we surely know it is part of the result; subtract tree[8] of cumFre (we do not want to look for the same cumulative frequency again – we are looking for another cumulative frequency in the rest/another part of tree); halve bitMask and continue
Third iteration - tIdx is 12; tree[12] is greater than 9 (note that the tree frequencies corresponding to tIdx being 12 do not overlap with the frequencies 1-8 that we have already taken into account); halve bitMask and continue
Fourth iteration - tIdx is 10; tree[10] is less than 9, so we should update values; halve bitMask and continue
Fifth iteration - tIdx is 11; tree[11] is equal to 2; return index (tIdx)
2D BIT
BIT can be used as a multi-dimensional data structure. Suppose you have a plane with dots (with non-negative coordinates). There are three queries at your disposal:
set a dot at (x , y)
remove the dot from (x , y)
count the number of dots in rectangle (0 , 0), (x , y) – where (0 , 0) is down-left corner, (x , y) is up-right corner and sides are parallel to x-axis and y-axis.
Ifmis the number of queries,max_xis the maximum x coordinate, andmax_yis the maximum y coordinate, then this problem can be solved in O(m * log (max_x) * log (max_y)) time as follows. Each element of the tree will contain an array of dimension max_y, that is yet another BIT. Hence, the overall structure is instantiated astree[max_x][max_y]. Updating indices of x-coordinate is the same as before. For example, suppose we are setting/removing dot (a,b). We will callupdate(a , b , 1)/update(a , b , -1), whereupdateis:
Lazy Modification
So far we have presented BIT as a structure which is entirely allocated in memory during the initialization. An advantage of this approach is that accessing tree[idx] requires a constant time. On the other hand, we might need to access only tree[idx] for a couple of different values of idx, e.g. log n different values, while we allocate much larger memory. This is especially aparent in the cases when we work with multidimensional BIT.
To alleviate this issue, we can allocate the cells of a BIT in a lazy manner, i.e. allocate when they are needed. For instance, in the case of 2D, instead of defining BIT tree as a two-dimensional array, in C++ we could define it as map<pair<int, int>, int>. Then, accessing the cell at position (x, y) is done by invoking tree[make_pair(x, y)]. This means that those (x, y) pairs that are never needed will never be created. Since every query visits O(log (max_x) * log (max_y)) cells, if we invoke q queries the number of allocated cells will be O(q log (max_x) * log (max_y)).
However, now accessing (x, y) requires logarithmic time in the size of the corresponding map structure representing the tree, compared to only constant time previously. So, by losing a logarithmic factor in the running time we can obtain memory-wise very efficient data structure that per query uses only O(log (max_x) * log (max_y)) memory in 2D case, or only O(log MaxIdx) memory in the 1D case.
binary indexed tree is a complex data structure. A data structure is a special format for organizing and storing data, simple data structures such as lists [], dictionaries {} and sets are very common examples.
binary indexed tree is a bitwise data structure based on the binary tree that is developed specifically for storing cumulative frequencies. it precomputes input numbers for a faster computation of cumulative.This structure uses a special algorithm (binary tree) to build a compressed binary indexed tree that prepares and stores these pre-processed numbers in an array of arrays (tree of arrays) and index them via binary codes (each node of tree stores the cumulative sum of all the values including that node and its left subtree) so that cumulative of a number or any other cumulative based query , e.g.finding difference of two cumulative, sum of a couple of numbers or updating a value in the array, can be done faster for large arrays.
lets see an example:
List = [1,2,3,4,5,6,7,8,9,10,11,12]
imagine we want to calculate sum of values from index 7 to 9 (=8+9)
a simple way is to subtract the two cumulative: 45 - 28 but for this you always need to keep a list of cumulative and the time it takes is proportional to the length of the array (N). in binary indexed tree you can get same result at less time (logN) by finding and adding specific indexed values via this formula:
Using a Fenwick tree it is very easy to generate the cumulative sum table. From this cumulative sum table it is possible to calculate the summation of the frequencies in a certain range in order of.
intA[SIZE];intsum(inti)// Returns the sum from index 1 to i{intsum=0;while(i>0)sum+=A[i],i-=i&-i;returnsum;}voidadd(inti,intk)// Adds k to element with index i{while(i<SIZE)A[i]+=k,i+=i&-i;}
after the observation that the binary representation of indices determines the implicit tree structure,
The problem - we want to be able to perform two operations on it: either changing the value stored at an index i, or calculating the sum of a prefix of length n.
Unlike most other data structures that solve this problem, Fenwick trees require no additional memory!
An intermediate representation
Consider, as an example, an array a of length 8. We can speed up prefix sum calculations by grouping the elements of the array by pairs, and storing the sum of each pair in a new array of length 4. Then we can repeat the procedure on that new array to obtain an array of length 2, and so on. This is illustrated in the figure below:
The result is a two-dimensional array-of-arrays called A (where A[0] contains the original array a). We can use this to calculate prefix sums quickly, by taking at most one element from each row, and adding these values together. For example, the sum of the first five elements can be calculated as: A[0][4] + A[2][0] == 5 + 9 == 14.
It is easy to tell visually which blocks must be added together to find a prefix sum. The process can be described more formally as follows. Start at row r=0 with prefix length n. If n is odd, then we need to add A[r][n-1] to the sum. In any case, we divide n by 2 and move down a row by incrementing r to 1. Then, we check again if n is odd, and if so, we add A[r][n-1]. This process is repeated until the bottom of the table is reached.
Updating values works in a similar manner: if we add/subtract a value in the original array, we must add/subtract that value to all blocks in the same column (one block per row) to keep the calculated sums consistent. Since every block is twice as wide as the one before it, we need to divide the index by two for each row.
functionupdate(i, v) { for (varr = 0; r < A.length; ++r) { A[r][i] += v; i >>= 1; } }
functionprefixsum(n) { varsum = 0; for (varr = 0; r < A.length; ++r) { if (n&1) sum += A[r][n - 1]; n >>= 1; } returnsum; }
This intermediate representation already provides the O(log n) time bounds that we desired, which follows from the fact that we need only 2log n + 1 rows for an array of n elements and the observation that we access (at most) one element in each row for each operation. The only problem left is that this representation requires twice as much memory to store the array-of-arrays A.
Optimizing for space
So where does Fenwick's space optimization come from? If we look carefully at the code used to calculate prefix sums, we see that we only access array elements at even indices, since we first check if n is odd (n&1) and if so, we add the element at index n-1 of the corresponding row, which must therefore be even.
That means that for each row we store, half the elements in the array are completely useless: the elements at odd indices are never used to calculate prefix sums! We can recycle this wasted space by storing the elements of A[1] at the odd indices of A[0], storing the elements of A[2] at the odd indices of A[1], and so on, until all relevant data is actually stored in the topmost array.
This compact array representation is called a Fenwick tree (though arguably Fenwick array would have been a more appropriate term) and is illustrated in the following figure:
This representation is nice because it allowed us to reduce the array-of-arrays A to a single, flat array a, no larger than the original array, yet we can still calculate prefix sums by adding the appropriate values, though they are now stored at different locations:
Think of the statement x&(-x) . It will give you the number generated by taking last occurring 1 with all the following 0’s in base 2 representation of the number x.
example: suppose x=20. Its binary representation will be 10100. x&(-x) will give you 100 ie 4.
Attention! So basically above example means that sum of box[1]….box[20] can be divided as sum of box[1]….box[16] +sum of box[17]….box[20] (as 20-16=4). So at this instant we want that BIT[16] to store cumulative sum from 1 to 16 and BIT[20] to store cumulative sum from 17 to 20 .
If we take x=22.Then sum of box[1]….box[22] will be divided into box[22]….box[21] +box[20]….box[17]+box[16]….box[1].So here we want that- BIT[22]=box[22]….box[21] BIT[20]=box[20]….box[17] BIT[16]=box[16]….box[1]
To get the positions of the array do this: i=x; i=i- (i&-i);
22 – (22 & (-22)) = 20
20 – (20 & (-20))= 16
16 – (16 & (-16))= 0
intBIT[100000];
voidinitializeBIT(intbox[],intn)//Array box[] is the given array.n is the size of the array
{
inti,k;
memset(BIT,0,sizeof(BIT)); //setting all elements to 0
for(i=1;i<=n;i++) //main loop
{
intvalue_to_be_added =box[i-1];
k=i;
while(k<=n)
{
BIT[k] +=value_to_be_added; //adding box[i-1] to all desired positions
k +=(k & (-k));
}
}
}
intquery(intR,intn)
{
intans=0;
intindex_till =R+1; //here R+1 is used because query is 0-based and BIT is 1-based
while(index_till >0)
{
ans +=BIT[index_till]; //Pulling segments to build answer
index_till-=(index_till & (-index_till));//getting the next desired array index
}
returnans;
}
voidupdate(intindex,intvalue,intn)
{
intindex_to_modify = index+1; //same reason,query is 0-based
while(index_to_modify <=n)
{
BIT[index_to_modify] +=value; //modifying all the necessary locations
idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx - 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx isresponsible for indexes from (idx - 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).
Image 1.4 - tree with tree frequencies
Change frequency at some position and update tree The concept is to update tree frequency at all indexes which are responsible for frequency whose value we are changing. In reading cumulative frequency at some index, we were removing the last bit and going on. In changing some frequencyval in tree, we should increment value at the current index (the starting index is always the one whose frequency is changed) for val, add the last digit to index and go on while the index is less than or equal to MaxVal.
void update(int idx ,int val){
while(idx <= N){
res[idx]+= val;
idx +=(idx &-idx);
}
}
void updateRange(int start,int end,int value ){
update( start, value );
update( end+1,-value );
}
Image 1.6 - Updating tree (in brackets are tree frequencies before updating); arrows show path while we update tree from index to MaxVal (image shows example for index 5)
Read cumulative frequency If we want to read cumulative frequency for some integer idx, we add to sum tree[idx], substract last bit of idx from itself (also we can write - remove the last digit; change the last digit to zero) and repeat this while idx is greater than zero
Image 1.5 - arrows show path from index to zero which we use to get sum (image shows example for index 13)
publicintrsq(int ind){assert ind >0;int sum =0;while(ind >0){ sum += array[ind];//Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number ind -= ind &(-ind);}return sum;}
/** * Range Sum Query from a to b. * Search for the sum from array index from a to b * a and b are 1-indexed * <p/> * Time-Complexity: O(log(n)) */publicintrsq(int a,int b){assert b >= a && a >0&& b >0;returnrsq(b)-rsq(a -1);}/** * Update the array at ind and all the affected regions above ind. * ind is 1-indexed * <p/> * Time-Complexity: O(log(n)) */publicvoidupdate(int ind,int value){assert ind >0;while(ind < array.length){ array[ind]+= value;//Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number ind += ind &(-ind);}}
.
![\sum_{i=1}^N a[i]](https://upload.wikimedia.org/math/5/8/4/584c01c46478dffe78795b5737598683.png)
