# segtree

Sep 20th, 2020
766
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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