Skip to content

Instantly share code, notes, and snippets.

View parthmittal's full-sized avatar

Parth Mittal parthmittal

  • New Delhi, India
View GitHub Profile
max_N = (1 << 20) #This is the maximum size of array our tree will support
seg = [0] * (4 * max_N) #Initialises the 'tree' to all zeroes.
def build(someList, v, L, R):
global seg
if (L == R):
seg[v] = someList[L]
else:
mid = (L + R) / 2 #Integer division is equivalent to flooring.
build(someList, 2 * v, L, mid)
@parthmittal
parthmittal / segment_tree.py
Last active June 20, 2018 10:14
A class implementing the segment tree data structure
class segment_tree:
"""A class which implements a range sum tree"""
def __init__(self, some_list):
"""
Initialises the tree, needs a list as a parameter
"""
self.N = len(some_list)
self.seg = [0] * (4 * len(some_list))