Advertisement
manish

segtree

Sep 20th, 2020
980
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.85 KB | None | 0 0
  1. from math import log2
  2.  
  3.  
  4. class SegmentTree:
  5.     def __init__(self, array):
  6.         self.n = len(array)
  7.         self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
  8.         self.default = None
  9.         self.data = [self.default] * (2 * self.size)
  10.         self.lazy = [None] * (2 * self.size)
  11.         self.process(array)
  12.  
  13.     def process(self, array):
  14.         self.data[self.size : self.size+self.n] = array
  15.  
  16.     def push(self, index):
  17.         """Push information of root to it's children!"""
  18.         if self.lazy[index] is None:return
  19.         self.lazy[2 * index] = self.lazy[index]
  20.         self.lazy[2 * index + 1] = self.lazy[index]
  21.         self.data[2 * index] = self.lazy[index]
  22.         self.data[2 * index + 1] = self.lazy[index]
  23.         self.lazy[index] = None
  24.  
  25.     def query(self, index):
  26.         """Returns the value at given index!"""
  27.         res = self.default
  28.         index += self.size
  29.         for i in reversed(range(1,index.bit_length())):
  30.             self.push(index >> i)
  31.         return self.data[index]
  32.  
  33.     def update(self, alpha, omega, value):
  34.         """Assign all elements in range (inclusive) to particular value."""
  35.         alpha += self.size
  36.         omega += self.size + 1
  37.         while alpha < omega:
  38.             if alpha & 1:
  39.                 self.data[alpha] = value
  40.                 self.lazy[alpha] = value
  41.                 alpha += 1
  42.             if omega & 1:
  43.                 omega -= 1
  44.                 self.data[omega] = value
  45.                 self.lazy[omega] = value
  46.             alpha >>= 1
  47.             omega >>= 1
  48.         self.push(self.size >> 1)
  49.  
  50. import sys
  51. input = sys.stdin.readline
  52. n, m = map(int, input().split())
  53. st = SegmentTree([0]*n)
  54. for _ in range(m):
  55.     a = list(map(int, input().split()))
  56.     if a[0] == 1:
  57.         st.update(a[1], a[2]-1, a[3])
  58.     else:
  59.         print(st.query(a[1]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement