CMX1P04 - Dark - Code Mates x1 Editorial

PROBLEM LINK:

Contest
Practice

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:

  1. Where you go to the past and change the value H[i] of ith house
  2. 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;
}
2 Likes

Fenwick tree (BI Tree)

Fenwick Tree (BIT) ruined