# HackerEarth Help the Avengers problem solution

In this HackerEarth Help the Avengers problem solution With the help of the tessaract, the Chitauri army is ready to attack planet Earth. It's finally time when the Avengers must get together to save the planet. Captain Fury, along with the beautiful Agent Maria Hill is trying to work out a plan. He is well aware that Loki, the leader of the enemies has identified certain prime spots to attack. Each spot on the planet is identified by a specific number. A prime spot is one that is represented by a prime number. Now, the Captain's intelligence team has provided him with a list of N locations A[1....N]. From time to time, the team also replaces one location in the list with another one. Every now and then, Captain Fury asks Maria to report the number of prime locations between positions X & Y (inclusive) in the list so that he could position the Avengers at those locations. Now the beautiful lady is tired. Help her.

## HackerEarth Help the Avengers problem solution.

`#include <bits/stdc++.h>using namespace std;bool vis [1000000 + 10];int siz = 0;int N = 1000000 + 10;void sieve(){                           // mark every number as prime or not    vis = true;    for(long long i = 2; i * i <= N; i++){        if(!vis[i]){                                    // check if the number is prime            for( long long j = i * i; j <= N; j+= i){                vis[j] = true;                          // mark the multiple of prime numbers as not prime            }        }    }}int arr [32000 + 10];int tree [32000 * 4 + 10];  // size = N * 4 = 200000 * 4void build (int index , int le , int ri){    if(le == ri){        tree[index] = !vis[arr[le]];                            // prime cells has a value of 1        return;    }    build(index * 2 + 1 , le , (le + ri) / 2);                 // build the left tree    build(index * 2 + 2,  (le + ri) / 2 + 1, ri );             // build the right tree    tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2];   // add the values of left , right trees    return;}void update (int index , int le , int ri , int target , int value){    if(le == ri){        tree[index] = !vis[value] ;                             // update the new value        return ;    }    if(target <= (le + ri) / 2 ){                                   // check if the position of the new value is on the left or right tree        update(index * 2 + 1, le , (le + ri) / 2, target, value);    } else {        update(index * 2 + 2, (le + ri) / 2 + 1 , ri , target, value);    }      tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2];          // add the updated left, right trees      return;}int query (int index , int le , int ri , int a , int b){    if(le >= a && ri <= b){                                             // check if the interval lies in the query        return tree[index];    }    if(le > b || ri < a) return 0;                                      // check if all of the interval is outside of the query    return query(index * 2 + 1, le , (le + ri) / 2 , a  ,  b) + query(index * 2 + 2, (le + ri) / 2 + 1, ri , a  ,  b);              // add the value of the left, right trees}int main(){    int t , n , q, tem1 , tem2;    char c;    sieve();    cin >> t;    while(t--){        cin >> n;        for(int i = 0; i < n; i++) cin >> arr[i];        build(0 , 0 , n - 1);        cin >> q;        for(int i = 0; i < q; i++){           cin >> c >> tem1 >> tem2;           if(c == 'C') update(0 , 0 , n - 1, tem1 - 1 , tem2);           else cout << query(0 , 0 , n - 1, tem1 - 1, tem2 - 1) << "\n";        }    }    return 0;}`