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)
		build(someList, 2 * v + 1, mid + 1, R)
		seg[v] = seg[2 * v] + seg[2 * v + 1]

def update(v, L, R, x, y):
	global seg
	if (L <= x <= R): #the index to be updated is part of this node
		if (L == R): #this is a leaf node
			seg[v] += y
		else:
			mid = (L + R) / 2
			update(2 * v, L, mid, x, y)
			update(2 * v + 1, mid + 1, R, x, y)

			#update node using new values of children
			seg[v] = seg[2 * v] + seg[2 * v + 1]

def query(v, L, R, x, y):
	if (R < x or y < L):
		#case 1
		return 0
	elif (x <= L <= R <= y):
		#case 2
		return seg[v]
	else:
		#case 3
		mid = (L + R) / 2
		return query(2 * v, L, mid, x, y) + query(2 * v + 1, mid + 1, R, x, y)

segment_tree_global_lazy.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.
lazy = [0] * (4 * max_N) #Initialises the lazy value of each node to zero.

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)
		build(someList, 2 * v + 1, mid + 1, R)
		seg[v] = seg[2 * v] + seg[2 * v + 1]

def update(v, L, R, x, y, z):
	global seg
	global lazy
	
	if (lazy[v]):
		#there are updates pending
		seg[v] += lazy[v] * (R - L + 1)
		if (L < R):
			#this is not a leaf node
			lazy[2 * v] += lazy[v]
			lazy[2 * v + 1] += lazy[v]
		#no more updates pending
		lazy[v] = 0

	if not (R < x or y < L):
		#eliminates case 1
		if (x <= L <= R <= y):
			#case 2
			seg[v] += (R - L + 1) * z
			lazy[2 * v] += z
			lazy[2 * v + 1] += z
		else:
			#case 3
			mid = (L + R) / 2
			update(2 * v, L, mid, x, y, z)
			update(2 * v + 1, mid + 1, R, x, y, z)

			seg[v] = seg[2 * v] + seg[2 * v + 1]

def query(v, L, R, x, y):
	global lazy
	global seg

	if (lazy[v]):
		#there are updates pending
		seg[v] += lazy[v] * (R - L + 1)
		if (L < R):
			#this is not a leaf node
			lazy[2 * v] += lazy[v]
			lazy[2 * v + 1] += lazy[v]
		#no more updates pending
		lazy[v] = 0	

	if (R < x or y < L):
		#case 1
		return 0
	elif (x <= L <= R <= y):
		#case 2
		return seg[v]
	else:
		#case 3
		mid = (L + R) / 2
		return query(2 * v, L, mid, x, y) + query(2 * v + 1, mid + 1, R, x, y)