SUBJECT-CHEF AND PANDEMIC -SEPT002- EDITORIAL
PROBLEM LINK
Author: codechefsrm
Editorialist : codechefsrm
DIFFICULTY
EASY
PREREQUISITES
Segment Tree
PROBLEM
In Chefland there has been a virus outbreak and the cities (numbered from 1 to N) have been affected from it.
Some cities were developed enough and made use of online technology to improve their economy while others suffered and experienced a loss.
You are given an array E where each E[i] is the initial economy of city i. As the president of Chefland , u want to answer to queries(Q) of two types
:Increase V C: In this u need to update the economy of city C by value V (add value V to the current economy of city C). You do not have to return anything.
Sum L R: Find the economy of the Cities in range [L,R] (both L and R are included) and print a singlevalue , the sum of economy of all these cities in a new line
EXPLANATION
We are given N countries with economy N each.
We have to answer queries, this is can be done using brute force but due to the constraints we wil have to use updation and sum query of segment tree.
Example Text Case
5
2 5 8 7 1
4
Increase 5 2
Sum 1 3
Increase 10 5
Sum 1 5
Output:
20
38
Here we use simple update query of segment tree for Increase and sum query of segment tree for finding Sum
SOLUTION :
Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
#define str string
#define pb push_back
#define ppb pop_back
#define ff first
#define ss second
#define vvi vector<vector<ll>>
#define vi vector<ll>
#define mapii map<ll,ll>
#define mapvi map<vector<ll>,ll>
#define mapiv map<ll,vector<ll>>
#define all(a) (a).begin(),(a).end()
#define show(arr,n) for(ll i=0;i<n;i++)cout<<arr[i]<<" ";
#define pii pair<ll,ll>
#define repi(x,n) for(ll i=x;i<n;++i)
#define repid(x,n) for(ll i=x;i>=n;--i)
#define repj(x,n) for(ll j=x;j<n;++j)
#define repjd(x,n) for(ll j=x;j>=n;--j)
#define print2(x,y) cout<<x<<" "<<y<<'\n'
#define print3(x,y,z) cout<<x<<" "<<y<<" "<<z<<'\n'
#define input(x) cin>>x
#define input2(x,y) cin>>x>>y
#define print(x) cout<<x<<'\n'
#define endl '\n'
#define M 1000000007
#define S 200005
#define E6 1000000
const ll INF = 1ll<<60;
using namespace std;
vi v(2000005,0);
vi tree(4000024,0);
void build(ll node, ll start, ll end)
{
if(start == end)
{
tree[node] = v[start];
}
else
{
ll mid = (start + end) / 2;
build(2*node, start, mid);
build(2*node+1, mid+1, end);
tree[node] = tree[2*node] + tree[2*node+1];
}
}
ll query(ll idx,ll st,ll end,ll l,ll r)
{
// comp inside
if(st>=l and end<=r)
return tree[idx];
//comp outside
else if(st>r or end<l)
return 0;
else
{
ll mid=(st+end)/2;
ll a=query(2*idx,st,mid,l,r);
ll b=query(2*idx+1,mid+1,end,l,r);
return a+b;
}
}
void update(ll idx,ll st, ll end,ll pos , ll val)
{
if(st==end)
{
tree[idx]+=val;
v[pos]+=val;
}
else
{
ll mid=(st+end)/2;
if(st<=pos and mid>=pos)
{
update(2*idx,st,mid,pos,val);
}
else
{
update(2*idx+1,mid+1,end,pos,val);
}
tree[idx]=tree[2*idx+1]+tree[2*idx];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll a;
ll n;
cin>>n;
for(ll i=1;i<n+1;i++)
{
input(a);
v[i]=a;
}
build(1,1,n);
ll q;
input(q);
while(q--)
{
str s;
ll x,y;
input(s);
if(s=="Increase")
{
ll val;
input(val);
ll pos;
cin>>pos;
update(1,1,n,pos,val);
}
else
{
input2(x,y);
ll ans;
ans=query(1,1,n,x,y);
print(ans);
}
}
return 0;
}