View segment_tree_global.py
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) |
View segment_tree.py
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)) |