Segment Tree | Sum of a given range

Segment Tree | Sum of a given range


A Segment Tree is a data structure that allows answering range queries over an array effectively. This includes

finding sum of consecutive array elements, minimum element in such a range and other problems.

Representation of Segment Tree:

  • Leaf nodes are elements of input array.
  • Each internal node represents some merging of leaf nodes, based on the problem under consideration.

An array representation of tree is used wherein every internal node has its child nodes at indices 2*i and 2*i+1.

Segment Tree representation for sample input:

Sample Output:
Array representation of tree : [0, 36, 32, 4, 12, 20, 1, 3 , 5, 7, 9, 11]
Sum of elements in the interval [1,3] : 15


#The following implementation can be extended for other Segment tree problems as well.
class SegmentTree:
def __init__(self):
self.tree =

#Function to build tree
def buildTree(self,List):
n = len(List)
self.tree = [
0 for i in range(2*n)]

#Initialize leaf nodes
for i in range(n):
self.tree[i+n] = List[i]

#Calculate parents and build the tree
for i in range(n-1,0,-1):
self.tree[i] = self.tree[i<<
1] + self.tree[i<<1 | 1]

#The function takes the new value and left and right indices as arguments and

#updates the nodes in the given range
def updateInRange(self, value, left, right):
n = len(self.tree)//

for i in range(left+n, right+n+1):
#Update the leaf node
self.tree[i] += value

j = i
#Move upwards and update parents
while j>1:
1] = self.tree[j] + self.tree[j^1]
j >>=

#The function takes the left and right indices as arguments and returns the sum
#in the index range [left,right)
def sumInRange(self, left, right):
n = len(self.tree)//
result =
left += n
right += n

#Add the current node to the sum iff its parent is not included in the same
#(resulting in faster computation of result)
while left<right:
#If left is odd then it means that it is the right child of it's parent
#and the interval includes only left and not it's parent. So, include
#this node to sum and move to the parent of it's next node.
#Similar condition is applied to right index.
if left&1:
result += self.tree[left]
left +=
if right&1:
right -=
result += self.tree[right]

left >>=
right >>=

return result

def main():
segmentTree = SegmentTree()

#Sample test case
sampleList = [

"Array representation of tree :",segmentTree.tree)
"Sum of elements in the interval [1,3] :",segmentTree.sumInRange(1,4))

if __name__ == "__main__":