PROBLEM LINK:
Setter: Uttkarsh Bawankar
Tester: Mayuresh Patle
Editorialist: Uttkarsh Bawankar
DIFFICULTY:
Easy
PREREQUISITES:
Segment Tree/ Fenwick tree (BI Tree)
PROBLEM:
Given N houses. Input the list of original wealth H[i] of these N households, where H[i] represents the wealth of ith house.
You need to process Q queries of two types:
- Where you go to the past and change the value H[i] of ith house
- Where you calculate the total wealth of houses in a given range L,R
EXPLANATION:
This is a straight forward segment-tree implementation without any alteration.
You can read this article by @anon55659401 to get the understanding of Segment Tree.
SOLUTIONS:
Setterās Solution: Recursive Implementation of Segment Tree
//author: utkd52
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define fi(n) for(int i=0;i<n;i++)
#define fj(n) for(int j=0;j<n;j++)
#define isEven(n) (!(n & 1))
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pi vector<int,int>
#define all(a) (a).begin(),(a).end()
#define USE_FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define USE_FILE_INPUT_OUTPUT freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
#define mod 1000000007
#define pmod 998244353
using namespace std;
void update(ll *sg, ll si,ll sl, ll sr, ll pos, ll diff)
{
if(sl>pos || sr<pos) return;
sg[si] += diff;
if(sl != sr)
{
ll mid = (sl+sr)/2;
update(sg, 2*si +1, sl, mid, pos, diff);
update(sg, 2*si +2, mid+1, sr, pos, diff);
}
}
ll range(ll *sg,ll si, ll sl, ll sr,ll l,ll r )
{
if(l<=sl && r>=sr) return sg[si];
if(sr<l || sl>r) return 0;
ll mid = (sl+sr)/2;
return (range(sg, 2*si +1, sl, mid, l, r) +range (sg, 2*si +2,mid+1, sr, l, r) );
}
ll con( ll *sg,ll si, ll *a, ll l, ll r)
{
if(l==r)
{
sg[si] = a[l];
return a[l];
}
ll mid = (l+r)/2;
sg[si] = con(sg, (2*si)+1, a, l , mid) + con(sg, (2*si)+2, a, mid+1 , r);
return sg[si];
}
int main()
{
//USE_FILE_INPUT_OUTPUT;
USE_FAST_IO;
ll h,w,ind,l,r,q,rep;
cin>>h;
ll a[h];
fi(h)cin>>a[i];
cin>>q;
string s;
rep = ceil(log2(h)) +1;
rep= pow(2,rep);
ll sg[rep];
con(sg, 0, a, 0, h-1);
while(q--)
{
cin>>s;
if(s=="past")
{
cin>>w>>ind;
ind--;
update(sg, 0, 0, h-1, ind, w);
}
else
{
cin>>l>>r;
ll ans = range(sg, 0, 0, h-1, l-1, r-1);
cout<<ans<<"\n";
}
}
}
Testerās Solution: Iterative Implementation of Segment Tree
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll st[2000001],n;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll i,w,l,r,q;
string s;
cin>>n;
for(i=0;i<n;++i) cin>>st[i+n];
for(i=n-1;i;--i) st[i]=st[i<<1]+st[i<<1|1];
cin>>q;
while(q--)
{
cin>>s;
if(s=="past")
{
cin>>w>>i;
for(st[i+=n-1]+=w;i;i>>=1) st[i>>1]=st[i]+st[i^1];
}
else
{
cin>>l>>r;
w=0;
for(l+=n-1,r+=n;l<r;l>>=1,r>>=1)
{
if(l&1) w+=st[l++];
if(r&1) w+=st[--r];
}
cout<<w<<"\n";
}
}
return 0;
}
Testerās Alternate Solution: Fenwick Tree
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ft[1000001],n;
void upd(ll i,ll v)
{
while(i<=n) ft[i]+=v,i+=i&(-i);
}
ll sum(ll i)
{
ll ans=0;
while(i) ans+=ft[i],i^=i&(-i);
return ans;
}
#define sum(l,r) sum(r)-sum(l-1)
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll i,w,l,r,q;
string s;
cin>>n;
for(i=1;i<=n;++i) cin>>w,upd(i,w); //add values to tree
cin>>q;
while(q--)
{
cin>>s;
if(s=="past")
{
cin>>w>>i;
upd(i,w); //update query
}
else
{
cin>>l>>r;
cout<<sum(l,r)<<"\n"; //sum query
}
}
return 0;
}