#2 GSS3 – Can you answer these queries III

Point Updates and Range Queries

  • Problem Statement: here
  • Roadmap: Segment Trees

This problem is online version of the GSS1 problem on SPOJ. I choose this version because we have already seen one offline segment tree problem. Here, again we need to figure out what can be the optimal elements to store for each node. The most common thing for Range Sum Queries is storing the Prefix and Suffix arrays.So, for each node here, we will store 4 different things :

  1. The answer to your interval [l,r]
  2. The maximum prefix sum of this interval [l,r] starting from l.
  3. The maximum suffix sum of this interval [l,r] starting from r.
  4. The total sum of this interval [l,r]

In the merging step, the way to merge nodes is : 

  1. The answers to your interval will be the maximum of 3 things
    1. your left ans
    2. your right ans
    3. maximum suffix sum of left + maximum prefix sum of right.
  2. The maximum prefix sum of your interval is maximum  of 2 things
    1. maximum prefix sum of left
    2. the total sum of left + maximum prefix sum of the right
  3. The maximum suffix sum of your interval is the maximum  of 2 things
    1. maximum suffix sum of the right
    2. the total sum of right + maximum suffix sum of left
  4. The total sum will obviously be the total sum of left + total sum of right.

We repeat similar logic while writing the update and query functions. 

Note that in the question, we are given point updates and range queries. There are questions, which can even involve point queries and range updates. We will look such questions, later in our series over segment trees.

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M1                  1000000007
#define M2                  998244353
#define ll                  long long int
#define pll                 pair<ll,ll>
#define mll                 map<ll,ll>
#define F                   first
#define S                   second
#define PB                  push_back
#define mp                  make_pair
#define lb                  lower_bound
#define ub                  upper_bound
#define V(a)                vector<a>
#define endl                '\n'
#define test(t)             while(t--)
#define PI                  acos(-1.0)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define repp(i,b,a)         for(ll i=b-1;i>=a;i--)
#define clr(ar, val)        memset(ar, val, sizeof(ar))
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define ps(y)               fixed << setprecision(y)
#define all(x)              begin(x),end(x)
#define allr(x)             rbegin(x),rend(x)
const int inf=              0x3f3f3f3f;
const ll INF=               0x3f3f3f3f3f3f3f3f;
const int dx[4]=            { 0, -1, 0, 1 };
const int dy[4]=            { -1, 0, 1, 0 };

ll floor_div(ll a, ll b) {
    return a / b - (((a ^ b) < 0) and a % b);
}
ll ceil_div(ll a, ll b){
    return a / b + (((a ^ b) >= 0) and a % b);
}

inline void INP()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);   
        freopen("output.txt","w",stdout);
    #endif 
}
ll ans[200005];
ll pms[200005];
ll sms[200005];
ll ts[200005];
ll a[50005];
void build(ll ind, ll l, ll r){
    if (l == r){
        ans[ind] = a[l];
        pms[ind]= a[l];
        sms[ind] = a[l]; 
        ts[ind] = a[l];
        return;
    }

    ll mid = (l+r)/2;
    build(2*ind, l, mid);
    build(2*ind + 1, mid+1, r);
    ans[ind] = max(ans[2*ind],max(ans[2*ind+1],sms[2*ind] + pms[2*ind + 1]));
    pms[ind] = max(pms[2*ind],ts[2*ind] + pms[2*ind+1]);
    sms[ind] = max(sms[2*ind +1], ts[2*ind+1] + sms[2*ind]);
    ts[ind] = ts[2*ind] + ts[2*ind+1];
}

pair<pll,pll> query(ll ind, ll l, ll r, ll qs, ll qe){
    if (qs > r || qe < l){
        return {{INT_MIN,INT_MIN},{INT_MIN,INT_MIN}};
    }
    if  (l >= qs &amp;&amp; r <= qe){
        return {{ans[ind],pms[ind]},{sms[ind],ts[ind]}};
    }

    ll mid = (l+r)/2;
    pair<pll,pll> left = query(2*ind,l,mid,qs,qe);
    pair<pll,pll> right = query(2*ind+1,mid+1,r,qs,qe);
    ll ans = max(left.F.F,max(right.F.F,left.S.F + right.F.S));
    ll prefmax = max(left.F.S, left.S.S + right.F.S);
    ll suffmax = max(right.S.F, right.S.S + left.S.F);
    ll totalsum = left.S.S +  right.S.S;
    return {{ans,prefmax},{suffmax,totalsum}}; 
}

void update(ll ind, ll l, ll r, ll val, ll tind){
    // Point Updates:
    if (tind <  l || tind > r){
        return;
    }
    if (l == r){
        ans[ind] = val;
        pms[ind] = val;
        sms[ind] = val;
        ts[ind] = val;
        return;
    }

    ll mid = (l+r)/2;
    update(2*ind, l, mid, val, tind);
    update(2*ind+1,mid+1,r,val,tind);
    ans[ind] = max(ans[2*ind],max(ans[2*ind+1],sms[2*ind] + pms[2*ind + 1]));
    pms[ind] = max(pms[2*ind],ts[2*ind] + pms[2*ind+1]);
    sms[ind] = max(sms[2*ind +1], ts[2*ind+1] + sms[2*ind]);
    ts[ind] = ts[2*ind] + ts[2*ind+1];
}

void solve()
{
    ll n;
    cin>>n;
    rep(i,0,n) cin >> a[i];
    build(1,0,n-1);
    ll m;
    cin >> m;
    rep(i,0,m){
        ll t,x,y;
        cin >> t >> x >>  y;
        if (t == 0){
            update(1,0,n-1,y,--x);
        }
        else{
            pair<pll,pll> res = query(1,0,n-1,--x,--y);
            cout << res.F.F << endl;
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    test(t){
        solve();
    }
    return 0;
}

Leave a Reply