# Segment tree problems

- 6 mins Different levels : `Beginner`, `Easy`, `Medium`, `Hard`, `Expert`

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

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

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].

Level: `Easy`

Problem 4.   Two types of operations can be here.

1. Query p, b means that you need to perform the assignment                            ap = b.

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

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

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].

Level: `Easy`

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

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 }

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].

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.

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 ai, ai+1, …, aj.

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.

Level: `Medium`

Problem 17.    Given a string (bracket sequence)

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

Level: `Medium`

Problem 18.    Given n ants with there strenths si.                                                When two ants i and j fight, ant i gets one battle point only if                          si divides sj . An ant i, with vi 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

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

Nx × Ny× Nz 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`