CDEC2209 - Editorial

editorial
, ,
#1

PROBLEM LINK:

Looks Easy - CDEC2209

Author: Nakshatra
Tester: Laksh Chauhan
Editorialist: Nakshatra

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment-tree (Segment tree | Efficient implementation - GeeksforGeeks)

PROBLEM:

Given array Ai and 2 queries.
In query 1, find the sum of subarray of the given range.
In query 2, updating the array.

QUICK EXPLANATION:

Brute force approach: Traversing the given range for every query which will have the time complexity O(q*n).
Efficient Approach: Using segment tree concept which will have the time complexity O(q+n)*logn.

EXPLANATION:

Efficient Approach:
First converting the given array to alternative negative terms as given in question that the alternate classroom will have rude professors.
Then building the segment tree.
For query 1: Just calculating the sum of the given range and if the initial index of given range is odd-indexed then the sum must be multiplied by -1 as odd indexed classroom contains rude professors.
For query 2: Simply update the segment tree.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

ll arr[100005], tree[4*100005];
void build(ll idx, ll low, ll high)
{
    if(low == high)
    {
        tree[idx] = arr[low];
        return;
    }

    ll mid = (high+low)/2;
    build((2*idx)+1, low, mid);
    build((2*idx)+2, mid+1, high);

    tree[idx] = tree[(2*idx)+1] + tree[(2*idx)+2];
}

ll query(ll idx, ll low, ll high, ll a, ll b)
{
    ll mid = (high+low)/2;
    if((b<low) || a>high)
        return 0;

    else if(a<=low && b>=high)
        return tree[idx];

    else
        return query((2*idx)+1, low, mid, a, b)+query((2*idx)+2, mid+1, high, a, b);
}

void update(ll idx, ll low, ll high, ll node, ll val)
{
    ll mid = (low + high)/2;
    if(low == high)
    {
        if(node%2)
            tree[idx] -= val;
        else
            tree[idx] += val;
    }

    else
    {
        if(node<=mid && node>=low)
            update((2*idx)+1, low, mid, node, val);

        else
            update((2*idx)+2, mid+1, high, node, val);

        tree[idx] = tree[(2*idx)+1] + tree[(2*idx)+2];
    }
}


int main()
{
    ll n;
    cin >> n;

    for(ll i=0; i<n; i++)
        cin >> arr[i];

    for(ll i=0; i<n; i++)
    {
        if(i%2)
            arr[i] = -1*arr[i];
    }

    build(0, 0, n-1);

    ll q;
    cin >> q;
    
    while(q--)
    {
        ll type;
        cin >> type;

        ll a, b;
        cin >> a >> b;

        if(type==1)
        {
            ll ans = query(0, 0, n-1, a, b);

            if(a%2)
                ans = -1*ans;

            if(ans < 0)
                cout << 0 << endl;

            else
                cout << ans << endl;
        }
        else
            update(0, 0, n-1, a, b);

    }

    return 0;
}