1.
Problem
1.1.
Example -
2.
Approach
3.
C++ Code
3.1.
Output:
4.
Algorithm Complexity
4.1.
Time Complexity
4.2.
Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Sum of Interval and Update with Number of Divisors

## Problem

Given an array ‘arr’ of length ‘N’. We have to implement two types of queries:

1. 1, ‘L’, ‘R’ - Update the segment from ‘L’ to ‘R’ by replacing every number with its number of divisors in that segment.
2. 2, ‘L’, ‘R’ - Find the sum of the numbers in the segment from ‘L’ to ‘R’.

#### Example -

Input:

N = 6

Q = 3

arr = [ 4, 12, 7, 8, 5, 9 ]

queries = [ { 2, 3, 5 }, { 1, 2, 4 }, { 2, 2, 5 } ]

Output:

20

17

Explanation:

1. The first query is of type 2, which means we have to find the sum in the segment [3, 5]. The elements in the segment are - [7, 8, 5]. Hence, the sum for this segment is 20.
2. The second query is of type 1, which means that we have to update the segment [2, 4] by replacing every number with its number of divisors. The elements of the segment are - [12, 7, 8]. We get - [6, 2, 4] by replacing every number with its number of divisors. The final array will be - [4, 6, 2, 4, 5, 9].
3. In the third query, we have to find the sum of elements from [2, 5]. The segment elements are - [6, 2, 4, 5]. Hence, the sum for this segment is 17.

## Approach

When we see range update and sum queries, the first thing that comes to mind is a Segment tree or a Fenwick tree. But in this problem, the update query isn’t that simple. We have to update a segment by replacing every number with its number of divisors. The sum query can be handled easily using the Fenwick tree.

We can notice that the number of divisors of 1 and 2 is 1 and 2 respectively. This means that we can ignore the updates on 1 and 2. For the remaining numbers, we can store the indexes of these numbers in a set. We can then only iterate on the numbers greater than two and perform updates by replacing every number with its number of divisors in that segment. If the number of divisors is <=2, we remove the index of that number from the set.

But how does this help in optimizing the time complexity? The upper bound of the number of divisors of a number is considered roughly O(N^) in practice. This means that a number of O(10*9) will take approximately 5-6 operations to reduce to a number <= 2. Therefore, if we only iterate on the numbers greater than two and reduce them, we can effectively solve the problem.

Since we also have to find the range sum of the array, we use the Fenwick tree such that the query(i) will return the sum of the array from index 1 to i. Thus, we can find the sum of the segment [l, r] by doing query(r) - query(l-1).

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

Live masterclass