# Binary Indexed Tree

How is this problem solved using Binary Indexed Tree?

I am trying to understand this solution using Binary Indexed Tree. But I am not able to understand this solution. I know Binary Indexed Tree is used for (Range Sum Query and Update Index).

Here is the link for the problem. https://www.codechef.com/problems/CHEFD

In Brief : We need to select number of elements in a array in range [L,R] which are divided by p(p is in range {2,3,5}) and divide those numbers by p. Also we have to update the number at index i by d. In last we have to print the final array.

Here is the solution.

``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;

#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
#define fordn(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define permute(x) next_permutation(all(x))
#define pb push_back

#define debug if(printf("JJ "))
#define MAX 100005

int bit2[MAX], bit3[MAX], bit5[MAX], arr[MAX];

void update(int tree[], int idx, int elem, int n) {
while (idx <= n)
{
tree[idx] += elem;
idx += (idx & (-idx));
}
}

void update(int tree[], int idxL, int idxR, int elem, int n) {
update(tree, idxL, elem, n);
update(tree, idxR + 1, -elem, n);
}

int query(int tree[], int idx, int n) {
int count = 0;
while (idx > 0)
{
count += tree[idx];
idx -= (idx & -idx);
}
return count;
}

int main() {
int q1, q2, q3, q4;
memset(bit2, 0, sizeof bit2);
memset(bit3, 0, sizeof bit3);
memset(bit5, 0, sizeof bit5);
int n, m;
cin >> n;
rep(i, n)
cin >> arr[i];

cin >> m;
while (m--) {
cin >> q1;
if (q1 == 1) {
cin >> q2 >> q3 >> q4;
if (q4 == 2)update(bit2, q2, q3, 1, n);
else if (q4 == 3)update(bit3, q2, q3, 1, n);
else if (q4 == 5)update(bit5, q2, q3, 1, n);
}
else {
cin >> q2 >> q3;
arr[q2 - 1] = q3;

int w = query(bit2, q2, n);
update(bit2, q2, q2, -w, n);

w = query(bit3, q2, n);
update(bit3, q2, q2, -w, n);

w = query(bit5, q2, n);
update(bit5, q2, q2, -w, n);
}
}
rep(k, n) {
int two = query(bit2, k + 1, n);
for (int i = 0; i < two && arr[k] % 2 == 0; i++) {
arr[k] /= 2;
}
int three = query(bit3, k + 1, n);
for (int i = 0; i < three && arr[k] % 3 == 0; i++) {
arr[k] /= 3;
}
int five = query(bit5, k + 1, n);
for (int i = 0; i < five && arr[k] % 5 == 0; i++) {
arr[k] /= 5;
}
// debug cout<<k<<" "<<two<<" "<<three<<" "<<five<<endl;
cout << arr[k] << " ";
}
puts("");
}
``````

I know we can solve this using set properties as well as segment tree. But I want to understand this using only and only Binary Indexed Tree.

Here I am not able to understand update as well as query function. Can anyone help me to understand this? Actually I am trying to understand this since last 4-5 hours. But some points I understood, others not. Can you please help me with this?

This BIT is 1-indexed BIT which supports range operation and point query. To understand how BIT works. Check this article out https://cp-algorithms.com/data_structures/fenwick.html.

And to understand this question, lets assume 3 different BITs to keep an record of update queries. For each update query of type [x, l, r], lets increment range [l, r] in tree_x by 1. Here x can be 2, 3 and 5. Hence we have 3 trees for each of them, tree_2, tree_3 and tree_5.
After processing all queries, lets traverse each element in array now. For each element k, query tree_2, tree_3 and tree_5 to check how many times [2, 3, 5] divides arr[k]. Finally peform dvision respectively and update arr[k].

Hope this helps

Let the Fenwick tree be initialized with zeros. Suppose that we want to increment the interval [l,r] by x. We make two point update operations on Fenwick tree which are `add(l, x)` and `add(r+1, -x)` . If we want to get the value of A[i] we just need to take the prefix sum using the ordinary range sum method. To see why this is true, we can just focus on the previous increment operation again. If i<l, then the two update operations have no effect on the query and we get the sum 00. If i∈[l,r] , then we get the answer x because of the first update operation. And if i>r, then the second update operation will cancel the effect of first one.