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. 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?

This BIT is 1-indexed BIT which supports range operation and point query. To understand how BIT works. Check this article out Fenwick Tree - Algorithms for Competitive Programming.

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 :slight_smile:

Very Helpful…

I have understood that we have to calculate how many times we need to divide our element of array using bit_2, but I am not able to understand why are we doing subtraction over here and also in update query why are we doing -w as well as in update function +w. Why is this?

We are doing this update +w and -w because this is how this type of BIT works. Check out the above mentioned link and read this particular section " Range Update and Point Query".

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.

I have got you thank you