<s> """<STR_LIT>""" <EOL> DEFAULT = <NUM_LIT:0> <EOL> f = lambda x , y : x + y <EOL> class Node ( object ) : <EOL> def __init__ ( self , start , end , m ) : <EOL> self . start , self . end , self . m = start , end , m <EOL> self . left , self . right = None , None <EOL> class SegmentTree ( object ) : <EOL> def __init__ ( self , A ) : <EOL> self . A = A <EOL> self . root = self . build_tree ( <NUM_LIT:0> , len ( self . A ) ) <EOL> def build_tree ( self , s , e ) : <EOL> """<STR_LIT>""" <EOL> if s >= e : <EOL> return None <EOL> if s + <NUM_LIT:1> == e : <EOL> return Node ( s , e , self . A [ s ] ) <EOL> left = self . build_tree ( s , ( s + e ) / <NUM_LIT:2> ) <EOL> right = self . build_tree ( ( s + e ) / <NUM_LIT:2> , e ) <EOL> val = DEFAULT <EOL> if left : val = f ( val , left . m ) <EOL> if right : val = f ( val , right . m ) <EOL> root = Node ( s , e , val ) <EOL> root . left = left <EOL> root . right = right <EOL> return root <EOL> def query ( self , root , s , e ) : <EOL> """<STR_LIT>""" <EOL> if not root : <EOL> return DEFAULT <EOL> if s <= root . start and e >= root . end : <EOL> return root . m <EOL> if s >= root . end or e <= root . start : <EOL> return DEFAULT <EOL> l = self . query ( root . left , s , e ) <EOL> r = self . query ( root . right , s , e ) <EOL> return f ( l , r ) <EOL> class Solution : <EOL> def intervalSum ( self , A , queries ) : <EOL> """<STR_LIT>""" <EOL> ret = [ ] <EOL> tree = SegmentTree ( A ) <EOL> for q in queries : <EOL> ret . append ( tree . query ( tree . root , q . start , q . end + <NUM_LIT:1> ) ) <EOL> return ret </s>
