Created
August 28, 2016 01:40
-
-
Save shahril96/bcb28499e0b45a643ecb0109d0417d83 to your computer and use it in GitHub Desktop.
Simple Binary Indexed Tree implementation (also called as Fenwick Tree)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
class BIT { | |
private: | |
vector<int> bit; | |
int n; | |
public: | |
BIT(int arr[], int n) { | |
this->bit.reserve(n*2); | |
this->bit.assign(n*2, 0); | |
this->n = n; | |
for(int i = 0; i < n; i++) { | |
updateBIT(i, arr[i]); | |
} | |
} | |
void updateBIT(int i, int val) { | |
i++; // index starts from 1 | |
while(i <= n) { | |
bit[i] += val; | |
i += i & -i; | |
} | |
} | |
int getSum(int i, int j) { | |
i++, j++; // index starts from 1 | |
if(i == 1) { | |
int sum = 0; | |
while(j > 0) { | |
sum += bit[j]; | |
j -= j & -j; | |
} | |
return sum; | |
} | |
return getSum(0, j-1) - getSum(0, i-2); // parameter used zero-based indexing | |
} | |
int getSum(int i) { | |
return getSum(0, i); | |
} | |
}; | |
int main() { | |
int arr[] = {1,1,1,2,1}; | |
int size = sizeof arr / sizeof arr[0]; | |
BIT bit(arr, size); | |
cout << bit.getSum(2,3) << endl; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment