# Segment tree problems

- 6 mins**Different levels :** `Beginner`

, `Easy`

, `Medium`

, `Hard`

, `Expert`

**Problem 1.** Query minimum value in [l,r].

1082 - Array Queries - LightOJ

**Level**: `Beginner`

**Problem 2.** Two types of operations can be here.

1. *Invert the bit from [i,j]*

2. *Answer whether the ith bit is 0 or 1*

1080 - Binary Simulation - LightOJ

**Level**: `Easy`

**Problem 3.** Three types of operations can be here.

1. *Query index id and Update index id to zero.*

2. *Add index id with value v.*

3. *Query sum in [l,r].*

1112 - Curious Robin Hood - LightOJ

**Level**: `Easy`

**Problem 4.** Two types of operations can be here.

1. *Query p, b means that you need to perform the assignment a _{p} = b.*

2. *Output the value ‘v’ ( calculated by alternate ‘or’ and ‘xor’).*

Xenia and Bit Operations - CODEFORCES (Div.2) D

**Level**: `Medium`

**Problem 5.** Two types of operations can be here.

1. *Each query giving two integer L and R, denoting the time hunter will be in forest.*

2. *Query the maximum number of segments that could be hit by any one of point from L to R*

BGSHOOT - Shoot and kill - SPOJ

**Level**: `Medium`

**Problem 6.** Two types of operations can be here.

1. *Add v to all numbers in the range of [l,r]*

2. *Query sum in [l,r].*

HORRIBLE - Horrible Queries - SPOJ

**Level**: `Easy`

**Problem 7.** Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }.

GSS1 - Can you answer these queries I - SPOJ

**Level**: `Medium`

**Problem 8.** Two types of operations can be here.

1. *Modify the i-th element with value v.*

2. *Query(x,y) = Max { a[i]+a[i+1]+…+a[j] ; x ≤ i ≤ j ≤ y }.* GSS3 - Can you answer these queries III - SPOJ

**Level**: `Medium`

**Problem 9.** Query(x1,y1,x2,y2) = Max {A[i]+A[i+1]+…+A[j] } where

x1 <= i <= y1 , x2 <= j <= y2 and x1 <= x2 , y1 <= y2 }

GSS5 - Can you answer these queries V - SPOJ

**Level**: `Hard`

**Problem 10.** Two types of operations can be here.

1. *Set the value of A[i] to x.*

2. *Find i and j such that x ≤ i, j ≤ y and i != j, such that the sum A[i]+A[j] is maximized.*

**Level**: `Medium`

**Problem 11.** Two types of operations can be here.

1. *Apply the xor operation with a given number x to each array element on the segment [l, r].*

2. *Query sum in [l,r].*

XOR on Segment - CODEFORCES Round #149 (Div. 2) E

**Level**: `Hard`

**Problem 12.** *Given Ranges of the form li ri, denoting the numbers of the leftmost and rightmost sections covered by the i-th poster.*

*Output the number of posters with visible sections.*

POSTERS - Election Posters - SPOJ

**Level**: `Medium`

**Problem 13.** Two types of operations can be here.

1. *Change the i-th bracket into the opposite one.*

2. *Check – if the word is a correct bracket expression.*

**Level**: `Medium`

**Problem 14.** Two types of operations can be here.

1. *Invert switched between [l,r]*

2. *Count how many lights are on in the range [l,r]*

**Level**: `Medium`

**Problem 15.** Two types of operations can be here.

1. *Online Queries*

2. *For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence a _{i}, a_{i+1}, …, a_{j}.*

KQUERYO - K-Query Online - SPOJ

**Level**: `Hard`

**Problem 16.** Two types of operations can be here.

1. *change all numbers in the range of x to y (inclusive) to v.*

2. *Count the number of primes between index x and y.*

CNTPRIME - Counting Primes - SPOJ

**Level**: `Medium`

**Problem 17.** Given a string (bracket sequence)

1. *Count the length of the maximum correct bracket subsequence of sequence.*

(Div. 1) C. Sereja and Brackets - CODEFORCES

**Level**: `Medium`

**Problem 18.** Given n ants with there strenths s_{i}. When two ants i and j fight, ant i gets one battle point only if s_{i} divides s_{j} . An ant i, with v_{i} battle points obtained, is going to be freed only if vi = r - l

1. *Count how many ants is he going to eat if those ants fight*

(Div. 2) F. Ant colony - CODEFORCES- Round #271

**Level**: `Hard`

**Problem 19.** Given a string (bracket sequence)

1. *Count the length of the maximum correct bracket subsequence of sequence.*

2. Answer how many numbers between indices A and B

are divisible by 3.

**Level**: `Medium`

**Problem 20.** Given an arrangement consists of a cuboidal box of size

N_{x} × N_{y}× N_{z} made of unit cubes.

1. Range Update with val = 1 in X, Y ,Z axis.

2. Report the number of red plants (1) in the cuboidal region with (x1,y1,z1) and (x2,y2,z2)

**Level**: `Hard`