fork download 
  1. class SegmentTree:
  2.     def __init__(self, nums):
  3.         self.n = len(nums)
  4.         self.tree = [0] * (2 * self.n)
  5.         self.build(nums)
  6.  
  7.     def build(self, nums):
  8.         for i in range(self.n):
  9.             self.tree[self.n + i] = nums[i]
  10.         for i in range(self.n - 1, 0, -1):
  11.             self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
  12.         print(self.tree)
  13.  
  14.     def update(self, idx, val):
  15.         idx += self.n
  16.         self.tree[idx] = val
  17.         while idx > 1:
  18.             idx //= 2
  19.             self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]
  20.  
  21.     def query(self, l, r):
  22.         l += self.n
  23.         r += self.n
  24.         sums = 0
  25.         while l <= r:
  26.             if l % 2 == 1:
  27.                 sums += self.tree[l]
  28.                 l += 1
  29.             if r % 2 == 0:
  30.                 sums += self.tree[r]
  31.                 r -= 1
  32.             l //= 2
  33.             r //= 2
  34.         return sums
  35.  
  36.  
  37. nums = [1, 3, 5, 7, 9, 11]
  38. segment_tree = SegmentTree(nums)
  39. queries = [(0, 2), (1, 4), (2, 5)]
  40. for query in queries:
  41.     left, right = query
  42.     result = segment_tree.query(left, right)
  43.  
Success #stdin #stdout 0.02s 7296KB
comments (?)
stdin 
Standard input is empty
stdout 
[0, 36, 32, 4, 12, 20, 1, 3, 5, 7, 9, 11]
https://ideone.com/QIZ6K3
language:
Python (cpython 2.7.16)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!