## Algorithm

Problem Name: Data Structures - Library Query

In this HackerRank in Data Structures - Library Query solutions,

A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. Now, being the geek that you are, you thought of the following two queries which can be performed on these shelves.

• Change the number of books in one of the shelves.

• Obtain the number of books on the shelf having the kth rank within the range of shelves.

A shelf is said to have the kth rank if its position is k when the shelves are sorted based on the number of the books they contain, in ascending order.

Can you write a program to simulate the above queries?

Input Format
The first line contains a single integer T, denoting the number of test cases.
The first line of each test case contains an integer N denoting the number of shelves in the library.
The next line contains N space separated integers where the ith integer represents the number of books on the ith shelf where 1<=i<=N.
The next line contains an integer Q denoting the number of queries to be performed. Q lines follow with each line representing a query.
Queries can be of two types:

• 1 x k - Update the number of books in the xth shelf to k (1 <= x <= N).
• 0 x y k - Find the number of books on the shelf between the shelves x and y (both inclusive) with the kth rank (1 <= x <= y <= N, 1 <= k <= y-x+1).

Output Format
For every test case, output the results of the queries in a new line.

Constraints
1 <= T <= 5
1 <= N <= 104
1 <= Q <= 104
The number of books on each shelf is always guaranteed to be between 1 and 1000.

Sample Input

``````2
2
1 2
2
0 1 2 1
0 1 2 2
4
4 3 2 1
4
0 1 1 1
1 1 1
0 1 1 1
0 1 4 3
``````

Sample Output

``````1
2
4
1
2
``````

Explanation

There are two test cases :

1. The first test case contains only two shelves which can be represented as [1, 2]. Two queries are to be processed : i) The first query asks for smallest number of books between the 1st and 2nd shevles which is 1. ii) The second query asks for the 2nd smallest number of books between the 1st and 2nd shevles which is 2.
2. The second test case contains four shelves which can be represented as [4, 3, 2, 1]. Four queries are to be processed :

i) The first query asks for the smallest number of books in the 1st shelf which is 4.

ii) The second query updates the number of books in the 1st shelf to 1. Hence the shelves now look like [1, 3, 2, 1].

iii) The third query asks for the smallest number of books in the 1st shelf which is now 1. iv) The last query asks for the 3rd smallest number of books between the 1st and 4th shelves which is 2.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

int t;
scanf("%d", &t);

while (t--) {
int n;
scanf("%d", &n);
int s[n+1];

for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}

int qc;
scanf("%d", &qc);

while (qc--) {
int q;
for (int i = 0; i < 3; i++) {
scanf("%d", &q[i]);
}
if (q == 1) {
s[q] = q;
} else {
scanf("%d", &q);
int bc = {0};

for (int i = q; i <= q; i++) {
bc[s[i]]++;
}

int count = q;
for (int i = 1; i <= 1000; i++) {
count -= bc[i];
if (count <= 0) {
printf("%d\n", i);
break;
}
}
}
}
}

return 0;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
#define msg(x) cout << #x << " = " << x << endl
using namespace std;

const int maxN = 10224;
const int maxRoot = 2014;

int a[maxN], t, n, root;
vector bucket[maxRoot];

void update() {
int idx, val;
cin >> idx >> val;
idx--;
int bidx = idx / root;
for (int i = 0; i < bucket[bidx].size(); i++) {
if (bucket[bidx][i] == a[idx]) {
bucket[bidx][i] = a[idx] = val;
break;
}
}
sort(bucket[bidx].begin(), bucket[bidx].end());
}

void query() {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
vector tmp;
tmp.reserve(root + 10);
int lb = l/root + 1;
int rb = r/root - 1;
while (l/root == lb - 1 && l < r) {
tmp.push_back(a[l]);
l++;
}
while (r >= l && r/root == rb + 1) {
tmp.push_back(a[r]);
r--;
}
sort(tmp.begin(), tmp.end());
int lo = 1, hi = 1000; //worst algorithm ever
while (lo < hi) {
int mid = lo + hi >> 1;
int cnt = upper_bound(tmp.begin(), tmp.end(), mid) - tmp.begin();
for (int i = lb; i <= rb; i++) {
cnt += upper_bound(bucket[i].begin(), bucket[i].end(), mid) - bucket[i].begin();
}
if (cnt >= k) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << hi << "\n";
}

int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
root = sqrt(1.0 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i % root == 0) {
bucket[i / root].clear();
}
bucket[i / root].push_back(a[i]);
}
for (int i = 0; i < maxRoot; i++) {
sort(bucket[i].begin(), bucket[i].end());
}
int q;
cin >> q;
while (q--) {
int cmd;
cin >> cmd;
if (cmd == 1) {
update();
} else {
query();
}
}
}
return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {

public static class SumTree {
private int size;
private int[] tree;

public SumTree(int n) {
size = 1;
while (size <= n) {
size *= 2;
}
tree = new int[size * 2];
}

public void clear() {
Arrays.fill(tree, 0);
}

public void set(int index, int value){
index += size;
tree[index] = value;
while (index > 1) {
index /= 2;
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}

private int getSum(int v, int l, int r, int L, int R) {
if (l == L && r == R) {
return tree[v];
}

if (l > r) {
return 0;
}

int middle = (L + R) / 2;
return getSum(v * 2, l, Math.min(middle, r), L, middle) +
getSum(v * 2 + 1, Math.max(middle + 1, l), r, middle + 1, R);
}

public int getSum(int l, int r) {
return getSum(1, l, r, 0, size - 1);
}
}

public static void main(String[] args) throws IOException {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
new Solution().run();
}

StreamTokenizer in;
PrintWriter out;

private int nextInt() throws IOException {
in.nextToken();
return (int)in.nval;
}

private void run() throws IOException {
out = new PrintWriter(System.out);
solve();
out.flush();
}

private void solve() throws IOException {
int t = nextInt();
for (int i = 0; i < t; i++) {
doTest();
}
}

public Solution() {
trees = new SumTree;
for (int i = 0; i < trees.length; i++) {
trees[i] = new SumTree(10001);
}

blockTrees = new SumTree[blocks];
for (int i = 0; i < blockTrees.length; i++) {
blockTrees[i] = new SumTree(10001);
}
}

SumTree[] trees;
SumTree[] blockTrees;
int blockSize = 32;
int blocks = 32;

private void doTest() throws IOException {
int n = nextInt();

for (int i = 0; i < trees.length; i++) {
trees[i].clear();
}

for (int i = 0; i < blockTrees.length; i++) {
blockTrees[i].clear();
}

int[] shelves = new int[n + 1];
for (int i = 1; i <= n; i++) {
shelves[i] = nextInt();
trees[shelves[i]].set(i, 1);
blockTrees[shelves[i] / blockSize].set(i, 1);
}

int q = nextInt();
for (int i = 0; i < q; i++) {
int qType = nextInt();
if (qType == 1) {
int shelve = nextInt();
trees[shelves[shelve]].set(shelve, 0);
blockTrees[shelves[shelve] / blockSize].set(shelve, 0);
int k = nextInt();
shelves[shelve] = k;
trees[shelves[shelve]].set(shelve, 1);
blockTrees[shelves[shelve] / blockSize].set(shelve, 1);
} else {
int x = nextInt();
int y = nextInt();
int k = nextInt();
int count = 0;
for (int block = 0; block < blocks; block++) {
int blockCnt = blockTrees[block].getSum(x, y);
//System.out.println("block = " + Integer.valueOf(block) + ", blockCnt = " + Integer.valueOf(blockCnt) + ", count = " + Integer.valueOf(count));
if (count + blockCnt >= k) {
for (int shelve = block * blockSize;; shelve++) {
count += trees[shelve].getSum(x, y);
if (count >= k) {
out.println(shelve);
break;
}
}
break;
}
count += blockCnt;
}
}
}
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
"use strict";

const fs = require("fs");

process.stdin.resume();
process.stdin.setEncoding("utf-8");

let inputString = "";
let currentLine = 0;

process.stdin.on("data", inputStdin => {
inputString += inputStdin;
});

process.stdin.on("end", _ => {
inputString = inputString
.trim()
.split("\n")
.map(str => str.trim());

main();
});

return inputString[currentLine++];
}

const parse10 = s => parseInt(s, 10);

.split(" ")
.map(parse10);

const counts = new Array(1001);

function solve(n, shelves, queries) {
const ans = [];
for (let [t, x, y, z] of queries) {
--x;
if (t === 1) {
shelves[x] = y;
} else {
counts.fill(0);
--y;
--z;
for (let i = x; i <= y; ++i) {
++counts[shelves[i]];
}
let s = 0;
for (let i = 1; i <= 1000; ++i) {
if (s <= z && z < s + counts[i]) {
ans.push(i);
break;
}
s += counts[i];
}
}
}
return ans;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
while (t--) {
const queries = new Array(q);
for (let i = 0; i < q; ++i) {
}
const ans = solve(n, shelves, queries);
ws.write(ans.join('\n') + '\n');
}
ws.end();
}
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class FenwickTree2D:
def __init__(self, x,y):
self.size_x = x
self.size_y = y
self.data = [*self.size_y for _ in range(self.size_x)]

def sum(self, x1, y1):
if min(x1,y1) <= 0: return 0
s = 0
x = x1
while x >= 0:
y = y1
while y >= 0:
s += self.data[x][y]
y = (y & (y+1)) - 1
x = (x & (x+1)) - 1
return s

def sumrange(self, x1, y1, x2, y2):
return self.sum(x2, y2) \
- self.sum(x1-1, y2) - self.sum(x2, y1-1) \
+ self.sum(x1-1,y1-1)

assert min(x1,y1) > 0
x = x1
while x < self.size_x:
y = y1
while y < self.size_y:
self.data[x][y] += w
y |= y + 1
x |= x + 1

for t in range(int(input())):
N = int(input())
arr = list(map(int,input().split()))
t = FenwickTree2D(10001,1001)
for i in range(len(arr)):
Q = int(input())
for q in range(Q):
c = list(map(int,input().split()))
if c==1:
arr[c-1] = c
else:
def select(l,r,k):
lo,hi=1,1000
while lo < hi:
med = (hi+lo)//2
a = t.sumrange(l,0,r,med)
if a>=k:
hi = med
else:
lo = med+1

if not t.sumrange(l,0,r,lo) >= k:
raise ValueError
return lo
print(select(c,c,c))
``````
Copy The Code &