Skip to content

Instantly share code, notes, and snippets.

@parthmittal
Last active June 18, 2018 04:52
Show Gist options
  • Save parthmittal/cdd386f57df44c238ff9 to your computer and use it in GitHub Desktop.
Save parthmittal/cdd386f57df44c238ff9 to your computer and use it in GitHub Desktop.
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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment