Introduction
In the last article, we studied how Binary Indexed Trees work and how they can be implemented. If you haven’t read that article yet, I would highly suggest to first go and take a look at that article first here
Questions
BIT can be used in many questions and there are various techniques to use BIT as well. For example, it can be directly used to perform Range sum queries or it can be used as a hash array to solve questions like Inversion Count. I have discussed both these approaches in the video below in detail.
BIT Questions and Code
The C++ code of both the questions discussed in the video above is as follows.
Range Sum Query
Given an array of size N and Q queries
Solve two types of quereies
Type 1 : i x : replace ith index by value x
Type 2 : l r : find sum from l to r
Input
15 423 4 5 6 332 2 441 2 652 2 462 1 5
Output
115217323
Code
1#include<bits/stdc++.h>2using namespace std;34const int N = 1e5+10;5int bit[N];67void update(int i, int x){8 for(; i < N; i += (i&-i))9 bit[i] += x;10}1112int sum(int i){13 int ans = 0;14 for(; i > 0; i -= (i&-i))15 ans += bit[i];16 return ans;17}1819int main(){20 int n, q;21 cin >> n >> q;22 int a[n+10];23 for(int i = 1;i <= n; ++i){24 cin >> a[i];25 update(i, a[i]);26 }2728 while(q--){29 int type;30 cin >> type;31 if(type == 1){32 int i, x;33 cin >> i >> x;34 update(i, x - a[i]);35 a[i] = x;36 }37 else{38 int l, r;39 cin >> l >> r;40 cout << sum(r) - sum(l-1) << endl;41 }42 }43}
Inversion Count
Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. We need to count all such pairs.
Input
1528 4 9 2 8
Output
15
Input
152100000000 10000 10000000000 10 100000000
Output
15
Code
1#include<bits/stdc++.h>2using namespace std;34const int N = 1e5+10;5int bit[N];67void update(int i, int x){8 for(; i < N; i += (i&-i))9 bit[i] += x;10}1112int sum(int i){13 int ans = 0;14 for(; i > 0; i -= (i&-i))15 ans += bit[i];16 return ans;17}1819int main(){20 int n;21 cin >> n;22 long long a[n+10];23 map<long long,int> mp;24 for(int i = 1;i <= n; ++i){25 cin >> a[i];26 mp[a[i]];27 }282930 // compression of numbers for the case where a[i] > 10 ^ 631 int ptr = 1;32 for(auto &pr : mp){33 pr.second = ptr++;34 }3536 for(int i = 1; i <= n; ++i){37 a[i] = mp[a[i]];38 }3940 // Finding Inversion count414243 int inversion_ct = 0;44 for(int i = 1; i<= n; ++i){45 inversion_ct += (sum(N-5) - sum(a[i]));46 update(a[i], 1);47 }4849 cout << inversion_ct << endl;505152}
BIT Questions
Range Sumer Queries| Leetcode
Inversion Count| Spoj
Almost Difference | Codeforces
I hope you all found the article as well as the video helpful. If you have any questions or doubt you can comment on the youtube video itself. I try to reply to most of the doubt questions. Feel free to ping me on any social media. Links can be found at bottom of the page.
