Segment tree problems

- 6 mins

Different levels : Beginner, Easy, Medium, Hard, Expert

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

                     1082 - Array Queries - LightOJ

                     Solution - Github

                     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

                     Solution - Github

                     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

                      Solution - Github

                     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’).

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

                      Solution - Github

                     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

                      Solution - Github

                     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

                      Solution - Github

                     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

                     Solution - Github

                     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

                      Solution - Github

                     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

                      Solution - Github

                     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.

                      KGSS - Maximum Sum - SPOJ

                      Solution - Github

                     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

                      Solution - Github

                     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

                      Solution - Github

                     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.

                      BRCKTS - Brackets - SPOJ

                      Solution - Github

                      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]

                      LITE - Light Switching - SPOJ

                      Solution - Github

                      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.

                      KQUERYO - K-Query Online - SPOJ

                      Solution - Github

                      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

                      Solution - Github

                      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

                      Solution - Github

                      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

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

                      Solution - Github

                      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.

                      MULTQ3 - SPOJ

                      Solution - Github

                      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)

                      IOPC1207 - GM plants - SPOJ

                      Solution - Github

                      Level: Hard

Jaskamal Kainth

Jaskamal Kainth

J1K7_7 , Geek , Programmer , Mathematics && Computer Science

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google pinterest medium