GSS1.py

import sys
tree = [-1]*100000
val = [1]*100000
lazy = [0]*100000

def buildTree(node,st,ed):
	# global tree
	if st>ed:
		return

	if st==ed:
		tree[node] = val[st]
		return

	mid = st+(ed-st)/2
	buildTree(node*2+1,st,mid)
	buildTree(node*2+2,mid+1,ed)

	tree[node] = (tree[node*2+1]+tree[node*2+2])

def updateTree(node,st,ed,i,j,value):
	# global tree
	if st>ed:
		return

	if lazy[node]:
		tree[node] += lazy[node]*(ed-st+1)
		# print i,j
		if st!=ed:
			lazy[node*2+1] += lazy[node]
			lazy[node*2+2] += lazy[node] 

		lazy[node] = 0

	if st>ed or st>j or ed<i:
		return

	if st>=i and ed<=j:
		tree[node] += value*(ed-st+1)

		if st!=ed:
			lazy[node*2+1] += value
			lazy[node*2+2] += value
		return

	updateTree(node*2+1,st,(st+ed)/2,i,j,value)
	updateTree(node*2+2,1+((st+ed)/2),ed,i,j,value)

	tree[node] = (tree[node*2+1] + tree[node*2+2])

def queryTree(node,st,ed,i,j):
	print st,ed,i,j
	global tree
	if st>ed or st>j or ed<i:
		print -sys.maxint,"nega"
		return -sys.maxint

	if lazy[node]:
		tree[node] += lazy[node]*(ed-st+1)
		# print i,j

		if st!=ed:
			lazy[node*2+1] += lazy[node]
			lazy[node*2+2] += lazy[node] 

		lazy[node] = 0

	if st>=i and ed<=j:
		print tree[node],"tree"
		return tree[node]

	print max(queryTree(node*2+1,st,(st+ed)/2,i,j) , queryTree(node*2+2,(st+ed)/2+1,ed,i,j)),"maxi"
	return max(queryTree(node*2+1,st,(st+ed)/2,i,j) , queryTree(node*2+2,(st+ed)/2+1,ed,i,j))

def main():

	buildTree(0,0,19)#0 st ed
	print queryTree(0,0,19,0,5),"qyer"#node st ed i j val

	updateTree(0,0,19,0,6,5)
	print queryTree(0,0,19,0,19),"qyer"

	updateTree(0,0,19,7,10,12)
	print queryTree(0,0,19,0,19),"qyer"

	updateTree(0,0,19,10,19,100)
	print queryTree(0,0,19,0,5),"qyer"

main()