In this HackerEarth A range function problem solution You are given an array A of N integer elements.

You are also given Q queries where each query is one of the following types:

1ival: Update value of element at i-th index to val i.e. A[i] = val
2LR: Find the value of function sigma(i=L,R)sigma(j=i,R)sigma(k=i,j)A[k].


HackerEarth A range function problem solution


HackerEarth A range function problem solution.

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

string multiply(string num1, string num2)
{
    int len1 = num1.size();
    int len2 = num2.size();
    if (len1 == 0 || len2 == 0)
    return "0";
    vector<int> result(len1 + len2, 0);
    int i_n1 = 0;
    int i_n2 = 0;

    for (int i=len1-1; i>=0; i--)
    {
        int carry = 0;
        int n1 = num1[i] - '0';
        i_n2 = 0;
            
        for (int j=len2-1; j>=0; j--)
        {
            int n2 = num2[j] - '0';

            int sum = n1*n2 + result[i_n1 + i_n2] + carry;
            carry = sum/10;
            result[i_n1 + i_n2] = sum % 10;
 
            i_n2++;
        }

        if (carry > 0)
            result[i_n1 + i_n2] += carry;

        i_n1++;
    }

    int i = result.size() - 1;
    while (i>=0 && result[i] == 0)
    i--;

    if (i == -1)
    return "0";

    string s = "";
     
    while (i >= 0)
        s += std::to_string(result[i--]);
 
    return s;
}

string add(string str1, string str2)
{
    if (str1.length() > str2.length())
        swap(str1, str2);

    string str = "";

    int n1 = str1.length(), n2 = str2.length();

    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;
    for (int i=0; i<n1; i++)
    {

        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');

        carry = sum/10;
    }

    for (int i=n1; i<n2; i++)
    {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }

    if (carry)
        str.push_back(carry+'0');

    reverse(str.begin(), str.end());
 
    return str;
}

string sub(string str1, string str2)
{

    string str = "";

    int n1 = str1.length(), n2 = str2.length();

    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
 
    int carry = 0;

    for (int i = 0; i < n2; i++) {
 
        int sub
            = ((str1[i] - '0') - (str2[i] - '0') - carry);
        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str.push_back(sub + '0');
    }

    for (int i = n2; i < n1; i++) {
        int sub = ((str1[i] - '0') - carry);

        if (sub < 0) {
            sub = sub + 10;
            carry = 1;
        }
        else
            carry = 0;
 
        str.push_back(sub + '0');
    }
 
    reverse(str.begin(), str.end());
 
    return str;
}

string seg[400005][3];
string a[100000 + 1];

void build(int l, int r, int index, int ind)
{
    if(l == r){
        if(ind == 0)
            seg[index][ind] = a[l];
        else if(ind == 1)
        {
            seg[index][ind] = multiply(to_string(l), a[l]);
        }
        else if(ind == 2)
            seg[index][ind] = multiply(to_string(l*l), a[l]);
        return;
    }

    int mid = (l + r) >> 1;
    build(l, mid, 2*index + 1, ind);
    build(mid + 1, r, 2*index + 2, ind);
    seg[index][ind] = add(seg[2*index + 1][ind], seg[2*index + 2][ind]);
}

void update(int l, int r, int index, int ind, int x)
{
    if(r < x or x < l) return;
    if(l == r and l == x){
        if(ind == 0)
            seg[index][ind] = a[l];
        else if(ind == 1)
            seg[index][ind] = multiply(to_string(l), a[l]);
        else if(ind == 2)
            seg[index][ind] = multiply(to_string(l*l), a[l]);   
        return;     
    }

    int mid = (l + r) >> 1;
    update(l, mid, 2*index + 1, ind, x);
    update(mid + 1, r, 2*index + 2, ind, x);
    seg[index][ind] = add(seg[2*index + 1][ind], seg[2*index + 2][ind]);    
}

string query(int l, int r, int index, int ind, int ql, int qr)
{
    if(r < ql or qr < l) return "0";
    if(ql <= l and r <= qr) return seg[index][ind];

    int mid = (l + r) >> 1;
    string first = query(l, mid, 2*index + 1, ind, ql, qr);
    string second = query(mid + 1, r, 2*index + 2, ind, ql, qr);
    return add(first, second);
}

string cal(string temp)
{
    int len = temp.size();
    string answer = "";
    if(temp[0] == '0')
    {
        int i = 0;
        while(i < len and temp[i] == '0')
        {
            i++;
        }

        for(int j = i ; j < len ; j++)
        {
            answer += temp[j];
        }
    }
    else{
        answer = temp;
    }
    return answer;
}

void solve(){
    int n;
    cin >> n;
    assert(1 <= n and n <= 100000);

    for(int i = 1 ; i <= n ; i++){
        int tot;
        cin >> tot;
        assert(1 <= tot and tot <= 1000000);
        a[i] = to_string(tot);
    }

    for(int i = 0 ; i < 3 ; i++){
        build(1, n, 1, i);
    }

    int q;
    cin >> q;
    assert(1 <= q and q <= 1000);
    while(q--){
        int type;
        cin >> type;
        assert(1 <= type and type <= 2);
        if(type == 1){
            int ind;
            cin >> ind;
            assert(1 <= ind and ind <= n);
            int num;
            cin >> num;
            assert(1 <= num and num <= 1000000);
            string val;
            val = to_string(num);
            a[ind] = val;
            for(int i = 0 ; i < 3 ; i++){
                update(1, n, 1, i, ind);
            }
        }
        else if(type == 2){
            int l;
            int r;
            cin >> l >> r;
            assert(1 <= l and l <= r and r <= n);
            string temp = multiply(to_string(r + l), query(1, n, 1, 1, l, r));
            temp = add(temp, multiply(to_string(r + 1), query(1, n, 1, 0, l, r)));
            temp = sub(temp, query(1, n, 1, 2, l, r));
            temp = sub(temp, multiply(to_string(r*l + l), query(1, n, 1, 0, l, r)));
            cout << cal(temp) << endl;
        }
    }
}

signed main(){
    int t;
    cin >> t;
    assert(1 <= t and t <= 10);
    while(t--){
        solve();
    }
}