parthmittal
/ segment_tree_global.py
Last active Jun 18, 2018
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) |
parthmittal
/ segment_tree.py
Last active Jun 20, 2018
A class implementing the segment tree data structure
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)) |