Python and MULTQ3

general
, ,
1

I’m learning about segment tree and lazy propagation, and I’m not sure if there something wrong in my implementation or codechef is not fear enough for python.
I have attached my code so please if someone can help and tell me how improve it, would it be great!!
Thanks…

PYTHON3

def build(st,node,start,end):
    if start == end:
        st[node] = [1,0,0]
    else:
        mid = (start+end)//2
        build(st,2*node+1,start,mid)
        build(st,2*node+2,mid+1,end)

        st[node] = [st[2*node+1][0] + st[2*node+2][0],st[2*node+1][1] + st[2*node+2][1],st[2*node+1][2] + st[2*node+2][2]]

def query(st,node,start,end,l,r):
    if lazy[node] != 0:
        st[node][0],st[node][1],st[node][2] = st[node][2],st[node][0],st[node][1]
        if start != end:
            lazy[2*n+1] = 1
            lazy[2*n+2] = 1
        lazy[n] = 0
    if start > r or end < l:
        return 0
    if start >= l and end <= r:
        return st[node][0]
    mid = (start+end)//2
    left = query(st,2*node+1,start,mid,l,r)
    right = query(st,2*node+2,mid+1,end,l,r)
    return left+right

def update(st,node,start,end,l,r):
    if lazy[node] != 0:
        st[node][0],st[node][1],st[node][2] = st[node][2],st[node][0],st[node][1]
        if start != end:
            lazy[2*n+1] = 1
            lazy[2*n+2] = 1
        lazy[n] = 0
    if start > r or end < l:
        return
    if start >= l and end <= r:
        st[node][0],st[node][1],st[node][2] = st[node][2],st[node][0],st[node][1]
        #st[node] = [st[node][2],st[node][0],st[node][1]]
        if start != end:
            lazy[2*node+1] = 1
            lazy[2*node+2] = 1
        return
    else:
        mid = (start+end)//2
        update(st,2*node+1,start,mid,l,r)
        update(st,2*node+2,mid+1,end,l,r)
        st[node] = [st[2*node+1][0]+st[2*node+2][0],st[2*node+1][1]+st[2*node+2][1],st[2*node+1][2]+st[2*node+2][2]]
        return
n,q = map(int,input().split())
st = [None for _ in range(4*n)]
lazy = [0 for _ in range(4*n)]
build(st,0,0,n-1)
while q:
    entry = [int(i) for i in input().split()]
    if entry[0] == 1:
        print(query(st,0,0,n-1,entry[1],entry[2]))
    else:
        update(st,0,0,n-1,entry[1],entry[2])
    q-=1
2

I don’t suggest you to use Segment Tree, it’s just too slow with Python. BIT, sparse table, Trie… all works much better. Try to solve that problem with BIT, it’s fastest and easier to learn.
Edit: Just checked the problem, with given 0.137226 secs time limit it’s impossible to pass with Python.

3

You don’t need to pass st to update and query function. Maybe passing a large array takes a lot of time. try without passing st.

4

Thanks both for your answers, first vichitr you are right I wass passing this st unnecessary parameter but I think tieros is right Python is to slow for this exercise using Segment tree. But tieros my question now is, is good Fenwick tree for range update queries? I never has implemented it in this case I have used ST instead BIT for range update queries.
Thanks.

5

@yans Yes, BIT is fast and suitable for this case.