Point Updates in Merge Sort Trees

Hello, I have implemented the version of merge sort tree that can handle point updates and supports duplicate elements in the tree.

I have done it using C++ STL: Policy based data structures.

There is no implemented tree multiset in STL. So, I have used pair<T,int> as a key where the second element in pair is the time when item has been added, in order to maintain uniqueness of elements.

The time complexity summaries are as follows :

  • Build ComplexityO(n log^2 n)
  • Query ComplexityO( log^3 n)
  • Update ComplexityO( log^2 n)

The code queries the kth largest element in a range , similar to MKTHNUM in spoj but with an update part.

    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp> 
    #include <ext/pb_ds/tree_policy.hpp> 
    #define ll long long int
    #define lc                      ((n)<<1)
    #define rc                      ((n)<<1|1)
    #define pb push_back
    using namespace std;
    using namespace __gnu_pbds;
    
    typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, 
                 tree_order_statistics_node_update> pds; 
    
    
    ll n;
    const ll N=463005;
    vector <ll> arr(N);
    pds mst[N];
    
    void init(ll pp)
    {
        for(ll i=0;i<4*pp;i++)
        {
            mst[i].clear();
        }
    }
    
    void build(ll n,ll b,ll e)
    {
        if(b==e)
        {
            mst[n].insert({arr[b],b});
            return;
        }
        for(ll i=b;i<=e;i++)
            mst[n].insert({arr[i],i});
            
        ll mid=(b+e)/2;
        build(lc,b,mid);
        build(rc,mid+1,e);
    }
    
    ll query(ll n,ll b,ll e,ll i,ll j,ll v,ll idx)
    {
        if(b>j or e<i)  return 0;
        if(b>=i and e<=j)
        {
            ll k=mst[n].order_of_key({v,idx});
            return k;
        }
        ll mid=(b+e)/2;
        return query(lc,b,mid,i,j,v,idx) + query(rc,mid+1,e,i,j,v,idx);
    }
    
    void update(ll n,ll b,ll e,ll i,ll v,ll nw)
    {
        if(i<b or e<i)  return;
        if(b==i and e==i)
        {
            mst[n].erase(mst[n].find({v,i}));
            mst[n].insert({nw,i});
            return;
        }
        ll mid=(b+e)/2;
        update(lc,b,mid,i,v,nw);
        update(rc,mid+1,e,i,v,nw);
        mst[n].erase(mst[n].find({v,i}));
        mst[n].insert({nw,i});
    }
    
    int main()
    {
        
        ll test,i,j,queries;
        scanf("%lld",&test); // number of test cases
        while(test--)
        {
            
            scanf("%lld",&n);  //number of elements in the array
            init(n);        // initializing the policy based tree
            
            for(i=1;i<=n;i++)
            {
                scanf("%lld",&arr[i]);  //scanning the array
            }
            
            build(1,1,n);
            
            cin>>queries;       //number of queries
            while(queries--)
            {
                ll choice;
                scanf("%lld",&choice);      //if choice is 0 -> it represents query, choice 1 -> represents update
                if(choice==0)
                {
                    ll l,r,x;
                    scanf("%lld %lld %lld",&l,&r,&x);       //  the x-th number in sorted a[l ... r] segment
                    
                    ll low = mst[1].find_by_order(0)->first, high = mst[1].find_by_order(n-1)->first , mid, ans ;
                    
                    // binary search to find the x-th number
                    
                    while(low <= high) 
                    {
                        mid = low + high >> 1;
                        ll k = query(1,1,n,l,r,mid,1005);       // i have considered the highest element in the array to be 1000, change according to your program
                        if(k >=x ) 
                        {
                            ans = mid;
                            high = mid-1;
                        }
                        else low = mid+1;
                    }
                    
                    printf("%lld\n",ans);
                    
                }
                else
                {               
                    // Update the profit of the idx-th shop to x
                    
                    ll idx,x;
                    scanf("%lld %lld",&idx,&x);
                    update(1,1,n,idx,arr[idx],x);
                    arr[idx]=x;
                }
                
            }
            
        }
        return 0;
        
    }

Execution with sample test case : kQrfVe - Online C++0x Compiler & Debugging Tool - Ideone.com

Do comment if you find any mistake.

Thank You

26 Likes

Wow! Learnt a lot. Thank you

1 Like

If we do not have updates, then we can find kTH smallest number in log^2N with merge sort tree (i.e. we can avoid binary search).

1 Like

Yes, we can do that. I have implemented the update function here because there are not much implementation available in the internet about it. In case MKTHNUM would have come with an update function, we needed to do this.

Yup. Let me save it in my template.

1 Like

the post has been updated, I wrote wrong that query time complexity is O ( n log^3 n ), actually it would be O (log ^ 3 n) so would be update.

I had read about it but did not find the implementation anywhere.

Awesome post.

2 Likes

Wow !   Your post reminds me of the problem GIVEAWAY from SPOJ. If you can find some similarity with MKTHNUM, you might be interested in my solution for GIVEAWAY using the same concept (policy based data structure being used as multiset on each node of segment tree). Sorry for no comment in code (it is really old), but I am sure one who is familiar with segment tree can figure out what is going on.
Do put a star if you found the repo interesting, I keep on updating solutions to good problems there. :grin:

1 Like

Yes it is similar. I will try out the problem! :slight_smile:

1 Like

wow…amazing stuff!

1 Like

But your code gives TLE in problem GIVEAWAY.

Wow ! I am not sure how an accepted solution is giving TLE now ! If anyone could figure-out, that would be great. :slightly_smiling_face:

Upd: Even Codechef Seems to behave similarly. here @vijju123 any reasons for this behaviour on codechef ?

1 Like

in this ques. also your code gives TLE.
@suvro_coder Now How to optimize this sol. ??

1 Like

I think now constant optimizations are required …

But why ? Did they update testcases ? Because the complexity of algo seems good enough to pass .
P.S. I also tried using compiler optimizations.

That’s strange that it is giving tle after test 6. But in the comment section, many are saying that their Nlog^2(N) is not passing but NQ is passing. It is a strange behaviour.

Could have been done quicker using wavelet tree if all queries can be processed offline.
Build: O((n+q)log(q))
Update and query: O(log^2(q))

But the merge sort tree code can do the same online with little extra time complexity.

They might have updated the test cases. This can be the only explanation. :3

CodeChef: Practical coding for everyone .
no i don’t think so. as same ques. also on codechef. here also it will give TLE
but when u change your ordered_set<pair<int,int>> to ordered_set then it will give
A.C. this is so strange behaviour…

2 Likes

How do you handle duplicate keys using this ? (as it is supposed to be a set instead of a multiset) ?