Sum of Interval and Update with Number of Divisors

C++ Code

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

// Array to store the number of divisors of a number
int num_divisors[100];

// Array to create Fenwick Tree
int tree[100];

// Calculating number of divisors of a number
void getNumDivisors(){
    for (int i = 1; i < 100; i++) {
        for (int j = i; j < 100; j += i) {
            num_divisors[j]++;
        }
    }
}
 
// Function for updating a number in BIT
void update(int x, int val, int n){
    for (x; x <= n; x += x&-x) {
        tree[x] += val;
    }
}
 
// Function to calculate sum till index i
int query(int i)
{
    int s = 0;
    for (i; i > 0; i -= i&-i) {
        s += tree[i];
    }
    return s;
}

void solve(int arr[], vector<int> queries[], int n, int q){

    // Initializing a set
    set<int> s;
    for (int i = 1; i < n; i++) {
         
        // Inserting indexes of numbers > 2.
        if(arr[i] > 2) s.insert(i);
        update(i, arr[i], n);
    }
     
    for (int i = 0; i < q; i++) {
         
        // Handling type 1 query
        if (queries[i][0] == 1) {
            while (true) {
                 
                // Finding required index from set
                auto it = s.lower_bound(queries[i][1]);

                if(it == s.end() || *it > queries[i][2]) break;
                 
                queries[i][1] = *it;
                 
                // Replacing every number with its number of divisors
                update(*it, num_divisors[arr[*it]] - arr[*it], n);
                 
                arr[*it] = num_divisors[arr[*it]];
                 
                // If new value is <=2, remove the index
                if(arr[*it] <= 2) s.erase(*it);

                queries[i][1]++;
            }
        }
         
        // Handling type 2 (sum) queries
        else {
            int l = queries[i][1]-1;
            int r = queries[i][2]-1;
            cout << (query(queries[i][2]) - query(queries[i][1] - 1)) << endl;
        }
    }
}
 
// Driver Code
int main()
{

    // Calculating number of divisors for each number
    getNumDivisors();
     
    int q = 3;
    int n = 6;
    int arr[] = {4, 12, 7, 8, 5, 9};
    vector<int>queries[] = { { 2, 3, 5 }, { 1, 2, 4 }, { 2, 2, 5 } };

    solve(arr, queries, n, q);
     
    return 0;
}

Output:

22
17

Algorithm Complexity

Time Complexity

For a type 2 (sum) query - we are querying over BIT to calculate the sum. This will take O(logN).

For a type 1 (update) query, we are replacing every number with its number of divisors. The number of divisors is precomputed, so replacing a number will work in constant time. To find the index of the element that needs to be updated, we use a binary search over a set. So this will take O(logN) time.

Now, we can say that we are iterating over every number greater than 2, so this should take O(N) time for every query. But this is not true. We have already proved that a number of O(10^9) will become <= 2 in just 5 or 6 queries. This means that in the worst case, only the first 5 or 6 update queries will have O(N) updates, after which all the numbers will become <= 2. Thus, replacing every number with its number of divisors will be done in constant time.

Therefore, the total time complexity is O(QlogN).

Space Complexity

We are creating an array for implementing the Fenwick tree. This will take O(N) space complexity. We are also creating an array to store the number of divisors. Thus, this will take O(max(‘arr’)) space. Here max(‘arr’) denotes the maximum element of the array.

Therefore total space complexity is O(N + max(‘arr’)).

Check out this problem - Two Sum Problem

FAQs

1. What is a Binary Indexed Tree?
   A Binary Indexed Tree or Fenwick tree is a data structure that can efficiently update elements and calculate prefix sums of a list of numbers. It allows both the operations to be performed in time complexity of O(logN).
    
2. What is a set in c++, and how is it implemented?
   In C++, a set is an STL container used to store unique elements in sorted order. We can add/remove elements from O(logN) time set. In C++, sets are implemented using Binary Search Trees.

Key Takeaways

In this article, we discussed the approach to find the sum of a segment of an array and update a segment by replacing every number with its number of divisors for multiple queries. We used the Fenwick tree to perform query operations and a set to perform update operations. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, all the best for your future endeavors, and Keep Coding.