CDEC2209 - Editorial

Looks Easy - CDEC2209

Author: Nakshatra
Tester: Laksh Chauhan
Editorialist: Nakshatra

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;
}
``````