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. CHEFD Problem - CodeChef
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?