help-ashu-1

Ashu and Shanu are best buddies. One day Shanu gives Ashu a problem to test his intelligence.He gives him an array of N natural numbers and asks him to solve the following queries:-

Query 0:- modify the element present at index i to x.
Query 1:- count the number of even numbers in range l to r inclusive.
Query 2:- count the number of odd numbers in range l to r inclusive.    

input:
First line of the input contains the number N. Next line contains N natural numbers. 
Next line contains an integer Q followed by Q queries.
0 x y - modify the number at index x to y.  
1 x y - count the number of even numbers in range l to r inclusive.
2 x y - count the number of odd numbers in range l to r inclusive.  

Constraints:
1 ≤ N,Q ≤ 10^5
1 ≤ l ≤ r ≤ N  
0 ≤ Ai ≤ 10^9
1 ≤ x ≤ N
0 ≤ y ≤ 10^9

Note:- indexing starts from 1.

SAMPLE INPUT
6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

SAMPLE OUTPUT
2
2
4

Source: hackerearth | Difficulty: EASY
Tags: Bit manipulation

Data structures

Range queries

Segment trees revisited


Solutions:
import math


def update_tree(node, left, right, i, diff):
	tree[node][0] += diff[0]
	tree[node][1] += diff[1]

	if left == right:
		return

	mid = (left + right) / 2
	left_index = 2 * (node + 1) - 1
	right_index = 2 * (node + 1)

	if i <= mid:
		update_tree(left_index, left, mid, i, diff)
	else:
		update_tree(right_index, mid + 1, right, i, diff)


def update(i, k):
	old_val = nums[i]
	nums[i] = k

	if old_val % 2 == 0 and k % 2 == 1:
		diff = [-1, 1]
	elif old_val % 2 == 1 and k % 2 == 0:
		diff = [1, -1]
	else:
		return
	update_tree(0, 0, N - 1, i, diff)


def create_tree(node, left, right):

	if left == right:
		if nums[left] % 2 == 0:
			tree[node][0] += 1
		else:
			tree[node][1] += 1
		return

	left_index = 2 * (node + 1) - 1
	right_index = 2 * (node + 1)
	mid = (left + right) / 2
	create_tree(left_index, left, mid)
	create_tree(right_index, mid + 1, right)

	tree[node][0] = tree[left_index][0] + tree[right_index][0]
	tree[node][1] = tree[left_index][1] + tree[right_index][1]


def count(node, left, right, range):

	if range[0] == left and range[1] == right:
		return tree[node]

	mid = (left + right) / 2
	left_index = 2 * (node + 1) - 1
	right_index = 2 * (node + 1)

	if range[0] <= mid and range[1] <= mid:
		return count(left_index, left, mid, range)
	elif range[0] > mid and range[1] > mid:
		return count(right_index, mid + 1, right, range)
	else:
	#elif range[0] <= mid < range[1]:
		e1, o1 = count(left_index, left, mid, [range[0], mid])
		e2, o2 = count(right_index, mid + 1, right, [mid + 1, range[1]])
		return [e1 + e2, o1 + o2]


def preprocess(nums):
	create_tree(0, 0, N - 1)

N = eval(input())
nums = list(map(int, input().split()))
power = math.ceil(math.log(N, 2)) + 1
length = int((2 ** power) - 1)
tree = [[0, 0] for i in range(length)]
preprocess(nums)
Q = eval(input())

for q in range(Q):
	type, v1, v2 = list(map(int, input().split()))

	if type == 0:
		update(v1 - 1, v2)
	elif type == 1:
		print(count(0, 0, N - 1, [v1 - 1, v2 - 1])[0])
	else:
		print(count(0, 0, N - 1, [v1 - 1, v2 - 1])[1])


# -*- coding: utf-8 -*-
"""
Created on Wed Sep 30 10:23:54 2015

@author: gangireddy
"""

#high = n-1
def buildSegmentTree(entries, segmenttree, low, high, pos):
	#print low, high, pos    
	if low == high:
		segmenttree[pos] = (entries[low] % 2)
		return
	mid = (low + high) / 2
	buildSegmentTree(entries, segmenttree, low, mid, 2*pos+1)
	buildSegmentTree(entries, segmenttree, mid+1, high, 2*pos+2)
	segmenttree[pos] = segmenttree[2*pos+1] + segmenttree[2*pos+2]

def rangeOddQuery(segmenttree, query, low, high, pos):
	if query[0] > high or query[1] < low:
		return 0
	if query[0] <= low and query[1] >= high:
		return segmenttree[pos]
	mid = (low + high) / 2
	return rangeOddQuery(segmenttree, query, low, mid, 2*pos+1) + rangeOddQuery(segmenttree, query, mid+1, high, 2*pos+2)

def updateElement(segmenttree, index, low, high, pos, val):
	#print low, high, pos
	if low == high and high == index:
		segmenttree[pos] = (val % 2)
		return
	mid = (low + high) / 2
	if index <= mid:
		updateElement(segmenttree, index, low, mid, 2*pos+1, val)
	else:
		updateElement(segmenttree, index, mid+1, high, 2*pos+2, val)
	segmenttree[pos] = segmenttree[2*pos+1] + segmenttree[2*pos+2]
	
def next2thpower(v):
	v -= 1
	v |= v>>1
	v |= v>>2
	v |= v>>4
	v |= v>>8
	v |= v>>16
	v += 1
	return v

n = int(input())
arr = list(map(int, input().split()))
q = int(input())
#find 2's power next to n
newn = next2thpower(n)
#print newn, n
segtree = [0]*(2*newn-1)
#lazytree = [0]*(2*newn-1)
buildSegmentTree(arr, segtree, 0, n-1, 0)
#print segtree
for query in range(q):
	t, x, y = list(map(int, input().split()))
	if t == 0 and (arr[x-1] % 2 != y % 2):
		#print 'updating'
		arr[x-1] = y
		updateElement(segtree, x-1, 0, n-1, 0, y)
	if t == 1:
		print((y-x)+1 - rangeOddQuery(segtree, (x-1, y-1), 0, n-1, 0))
	if t == 2:
		print(rangeOddQuery(segtree, (x-1, y-1), 0, n-1, 0))


import math
def cretre(low,up,pos):
	global seg
	global arr
	if up == low:
		seg[pos] = arr[low]
		return 
	mid = (up+low)/2
	cretre(low,mid,2*pos+1)
	cretre(mid+1,up,2*pos+2)
	seg[pos] = seg[2*pos+1] +seg[2*pos+2]
	return
def query(low,up,mn,mx,pos):
	global seg
	if mn>=low and mx<= up:
		return seg[pos]
	elif mn>up or mx<low:
		return 0
	mid = (mx+mn)/2
	return query(low,up,mn,mid,2*pos+1)+query(low,up,mid+1,mx,2*pos+2)
def update(ind,pos,arrlow,arrup,y):
	global seg
	if arrup== arrlow:
		seg[pos] = y
		return
	mid = (arrup+arrlow)/2
	if ind<= mid:
		update(ind,2*pos+1,arrlow,mid,y)
	else:
		update(ind,2*pos+2,mid+1,arrup,y)
	seg[pos] = seg[2*pos+1]+seg[2*pos+2]
	return
n = eval(input())
arr = list(map(int,input().split()))
for x in range(n):
	arr[x] = arr[x]%2
u = int(math.ceil(math.log(n)/math.log(2)))
u = 2**(u+1)-1
seg = [0]*u
cretre(0,n-1,0)
#print seg
tst = eval(input())
for x in range(tst):
	q,x,y = list(map(int,input().split()))
	if q == 2:
		w = query(x-1,y-1,0,n-1,0)
		print(w)
	elif q == 1:
		w = query(x-1,y-1,0,n-1,0)
		print((y-x+1)-w)
	else:
		update(x-1,0,0,n-1,y%2)


import math
n = int(input())
a = [0] + list(map(int, input().split()))
temp = 2**(int(math.log(2*n-1,2))+1)-1
tree = [0]*(temp) #denoting odd numbers
lazy = [0]*(temp)

def build (node, start, end):
	#print node, start, end
	if (start == end):
		tree[node] = a[start]%2
	else:
		mid = (start+end)/2
		build(2*node, start, mid)
		build(2*node+1, mid+1, end)
		tree[node] = tree[2*node]+tree[2*node+1]

def update(node, start, end, idx, val):
	if (start == end):
		a[idx] = val
		tree[node] = val%2
	else:
		mid = (start+end)/2
		if (start <= idx and idx <=mid):
			update (2*node, start, mid, idx, val)
		else:
			update (2*node+1, mid+1, end, idx, val)
		tree[node] = tree[2*node] + tree[2*node+1]
		
def query(node, start, end, l, r):
	if (r<start or end<l):
		return 0
	elif (l <= start and end <= r):
		return tree[node]
	else:
		mid = (start+end)/2
		return query(2*node, start, mid, l, r)+query(2*node+1, mid+1, end, l, r)

build(1,1,n)

for q in range(int(input())):
	c,l,r = list(map(int,input().split()))
	if (c==0):
		update(1,1,n,l,r)
	elif (c==1):
		print((r-l+1)-query(1,1,n,l,r))
	elif (c==2):
		print(query(1,1,n,l,r))