Point Updates in Merge Sort Trees

tutorial
, ,
6

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.

7

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

Awesome post.

2 Likes
8

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
9

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

1 Like
10

wow…amazing stuff!

1 Like
11

But your code gives TLE in problem GIVEAWAY.

12

Screenshot from 2020-03-29 16-16-27
Screenshot from 2020-03-29 16-16-271245Ă—751 103 KB

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
13

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

1 Like
14

I think now constant optimizations are required …

15

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

16

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.

17

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.

18

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

19

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
20

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

21

U have to assume all are distinct elements. i know this is totally wrong .
and when u submit the code on spoj also, then u will get AC by this assumption.
and in comments also it is mentioned.
I think both the questions have their proper solution using sqrt decomposition.

22

Maybe, but n log^2 n is better than n sqrt n. It should have worked.

1 Like
23

Variation of ~0.1seconds on resubmitting is common. But it does seem suspicious, I will ask admins to have a look.

3 Likes
24

thanks bro :slight_smile: learned a lot

25

merge sort trees using binary indexed tree
problem : CodeChef: Practical coding for everyone
if count small is false in query it will return kth smallest element in range [a,b]

#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;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,
tree_order_statistics_node_update> orderedmultiset;


int sz;
vector<orderedmultiset> bit;

int lowbit(int x){
    return x&-x;
}

void add(int i,int x){
    for(;i<=sz;i+=lowbit(i))
        bit[i].insert(x);
}

int query(int i,int x){
// count number strictly smaller than x till ith
    int count = 0;
    for( ; i > 0; i-=lowbit(i)){
        count += bit[i].order_of_key(x);
    }
    return count;
}

int query(int l,int r,int kth,bool cntsmall=false){

    if(cntsmall){
        return query(r,kth) - query(l-1,kth);
    }

    int low = 0, high = 10, ans = 0;
    while(low <= high){
        int mid = (low+high)/2;
        int cnt = query(r,mid) - query(l-1,mid);

        if(cnt < kth){
            ans = mid;
            low = mid+1;
        }else{
            high = mid-1;
        }
    }
    return ans;
}

void update(int i,int old,int newval){
    for(;i<=sz;i+=lowbit(i)){
        bit[i].erase(bit[i].upper_bound(old));
        bit[i].insert(newval);
    }
}

void build(vector<int> &v){
    sz = v.size();
    bit.resize(sz+1);
    for(int i=1;i<sz;i++){
        add(i,v[i]);
    }
}


void solve(){

    int n;
    cin >> n;
    
    vector<int> v(n+1);
    for(int i=1;i<=n;i++){
        cin >> v[i];
    }

    build(v);

    int q;
    cin >> q;
    while(q--){
        int type;
        cin >> type;
        if(type == 0){
            int l,r,x;
            cin >> l >> r >> x;
            cout<<( r-l+1 - query(l,r,x,true))<<endl;
        }
        else{
            int p,x;
            cin >> p >> x;
            update(p,v[p],x);
            v[p] = x;
        }
    }
}   

signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
    solve();
    return 0;
}