Segment Trees

A Segment Tree is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array. This includes finding the sum of consecutive array elements a[l…r], or finding the minimum element in a such a range in O(logn) time. Between answering such queries the Segment Tree allows modifying the array by replacing one element, or even change the elements of a whole subsegment (e.g. assigning all elements a[l…r] to any value, or adding a value to all element in the subsegment).

In general a Segment Tree is a very flexible data structure, and a huge number of problems can be solved with it. Additionally it is also possible to apply more complex operations and answer more complex queries (see Advanced versions of Segment Trees).

One important property of Segment Trees is, that they require only a linear amount of memory. The standard Segment Tree requires 4n vertices for working on an array of size n.

Query Results = O(logN), Updates = O(logN), Tree construction = O(N)

Left Child = 2*index, Right child = 2*index + 1

Question - 1

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

class NumArray {
    // A TreeNode stores sum of a range
    int[] tree, nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        tree = new int[4 * nums.length];
        if(nums.length==0)
            return;
        // O(N)
        buildTree(0, nums.length - 1, 1);
    }

    public void buildTree(int start, int end, int index) {
        if (start == end) {
            tree[index] = nums[start];
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(start, mid, 2 * index);
        buildTree(mid + 1, end, 2 * index + 1);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public void update(int i, int val) {
        // O(logN)
        update(0, nums.length - 1, 1, i, val);
    }

    public void update(int start, int end, int index, int updateIndex, int value) {
        if (start == end) {
            // At this point start == end == updateIndex
            nums[start] = tree[index] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        // Right call
        if (updateIndex > mid)
            update(mid + 1, end, 2 * index + 1, updateIndex, value);
        // Left call
        else
            update(start, mid, 2 * index, updateIndex, value);
        // Reflect changes in parent node
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public int sumRange(int i, int j) {
        return query(0, nums.length - 1, 1, i, j);
    }

    public int query(int start, int end, int index, int L, int R) {
        // No overlap
        if (start > R || end < L)
            return 0;
        // Complete overlap
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        int leftSum = query(start, mid, 2 * index, L, R);
        int rightSum = query(mid + 1, end, 2 * index + 1, L, R);
        return leftSum + rightSum;
    }
}

Question - 2

Given an array A of size N, there are two types of queries on this array.

1) l r: In this query you need to print the minimum in the sub-array A[l:r].

2) x y: In this query you need to update A[x]=y.

Examples:

Input: A={1, 3, 4, 2, 5} Queries: Type 1: L = 0, R = 2. Type 2: i = 1, val = 6 Type 1: L = 0, R = 2.
Output: 1 1

class Solution {
    public static void buildTree(int[] arr, int[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = Math.min(tree[2 * index], tree[2 * index + 1]);
    }

    public static int findMin(int[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return Integer.MAX_VALUE;
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        int leftMin = findMin(tree, start, mid, 2 * index, L, R);
        int rightMin = findMin(tree, mid + 1, end, 2 * index + 1, L, R);
        return Math.min(leftMin, rightMin);
    }

    public static void updateElement(int[] arr, int[] tree, int start, int end, int index, int updateIndex, int value) {
        if (start == end) {
            arr[start] = value;
            tree[index] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        if (updateIndex > mid)
            updateElement(arr, tree, mid + 1, end, 2 * index + 1, updateIndex, value);
        else
            updateElement(arr, tree, start, mid, 2 * index, updateIndex, value);
        tree[index] = Math.min(tree[2 * index], tree[2 * index + 1]);
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int tree[] = new int[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            if (query[0] == 1)
                System.out.println(findMin(tree, 0, n - 1, 1, query[1], query[2]));
            else
                updateElement(arr, tree, 0, n - 1, 1, query[1], query[2]);
        }
    }
}

Question - 3

Given an array of N positive integers. The task is to perform the following operations according to the type of query given. 1. Print the maximum pair product in a given range. [L-R] 2. Update Ai with some given value.

Examples:

Input: A={1, 3, 4, 2, 5} Queries: Type 1: L = 0, R = 2. Type 2: i = 1, val = 6 Type 1: L = 0, R = 2.
Output: 12 24
For the query1, the maximum product in a range [0, 2] is 3*4 = 12. For the query2, after an update, the array becomes [1, 6, 4, 2, 5] For the query3, the maximum product in a range [0, 2] is 6*4 = 24.

class Solution {
    static class Pair {
        int max, smax;

        Pair(int max, int smax) {
            this.max = max;
            this.smax = smax;
        }
    }

    public static void buildTree(int[] arr, Pair[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], Integer.MIN_VALUE);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

    public static Pair findMaxProd(Pair[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(Integer.MIN_VALUE, Integer.MIN_VALUE);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair leftPair = findMaxProd(tree, start, mid, 2 * index, L, R);
        Pair rightPair = findMaxProd(tree, mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(0, 0);
        ans.max = Math.max(leftPair.max, rightPair.max);
        ans.smax = Math.min(Math.max(leftPair.max, rightPair.smax), Math.max(leftPair.smax, rightPair.max));
        return ans;
    }

    public static void updateElement(int[] arr, Pair[] tree, int start, int end, int index, int updateIndex,
            int value) {
        if (start == end) {
            arr[start] = value;
            tree[index] = new Pair(value, Integer.MIN_VALUE);
            return;
        }
        int mid = start + (end - start) / 2;
        if (updateIndex > mid)
            updateElement(arr, tree, mid + 1, end, 2 * index + 1, updateIndex, value);
        else
            updateElement(arr, tree, start, mid, 2 * index, updateIndex, value);
        tree[index] = new Pair(0, 0);
        tree[index].max = Math.max(tree[2 * index].max, tree[2 * index + 1].max);
        tree[index].smax = Math.min(Math.max(tree[2 * index].max, tree[2 * index + 1].smax),
                Math.max(tree[2 * index].smax, tree[2 * index + 1].max));
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        Pair tree[] = new Pair[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            if (query[0] == 1) {
                Pair product = findMaxProd(tree, 0, n - 1, 1, query[1], query[2]);
                System.out.println(product.max * product.smax);
            } else
                updateElement(arr, tree, 0, n - 1, 1, query[1], query[2]);
        }
    }
}

Question - 4

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:

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

Given M queries, your program must output the results of these queries.

class Solution {
    static class Pair {
        int sum, mSum, bps, bss;

        // mSum -> max sum, bps -> best prefix sum, bss -> best suffix sum
        Pair(int s, int m, int bps, int bss) {
            this.sum = s;
            this.mSum = m;
            this.bps = bps;
            this.bss = bss;
        }
    }

    public static void buildTree(int[] arr, Pair[] tree, int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], arr[start], arr[start], arr[start]);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, tree, start, mid, 2 * index);
        buildTree(arr, tree, mid + 1, end, 2 * index + 1);
        tree[index] = new Pair(0, 0, 0, 0);
        tree[index].sum = tree[2 * index].sum + tree[2 * index + 1].sum;
        tree[index].mSum = Math.max(Math.max(tree[2 * index].mSum, tree[2 * index + 1].mSum),
                Math.max(
                        Math.max(tree[2 * index].sum + tree[2 * index + 1].bps,
                                tree[2 * index].bss + tree[2 * index + 1].sum),
                        tree[2 * index].bss + tree[2 * index + 1].bps));
        tree[index].bps = Math.max(tree[2 * index].bps, tree[2 * index].sum + tree[2 * index + 1].bps);
        tree[index].bss = Math.max(tree[2 * index + 1].bss, tree[2 * index].bss + tree[2 * index + 1].sum);
    }

    public static Pair findMaxProd(Pair[] tree, int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(-1000000, -1000000, -1000000, -1000000);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair leftPair = findMaxProd(tree, start, mid, 2 * index, L, R);
        Pair rightPair = findMaxProd(tree, mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(0, 0, 0, 0);
        ans.sum = leftPair.sum + rightPair.sum;
        ans.mSum = Math.max(Math.max(leftPair.mSum, rightPair.mSum), Math.max(
                Math.max(leftPair.sum + rightPair.bps, leftPair.bss + rightPair.sum), leftPair.bss + rightPair.bps));
        ans.bps = Math.max(leftPair.bps, leftPair.sum + rightPair.bps);
        ans.bss = Math.max(leftPair.bss + rightPair.sum, rightPair.bss);
        return ans;
    }

    public static void rangeQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        Pair tree[] = new Pair[4 * n];
        buildTree(arr, tree, 0, n - 1, 1);
        for (int[] query : queries) {
            System.out.println(findMaxProd(tree, 0, n - 1, 1, query[1], query[2]).mSum);
        }
    }
}

Question - 5

Segment trees are extremely useful. In particular "Lazy Propagation" (i.e. see here, for example) allows one to compute sums over a range in O(lg(n)), and update ranges in O(lg(n)) as well. In this problem you will compute something much harder:

The sum of squares over a range with range updates of 2 types:

1) increment in a range

2) set all numbers the same in a range.

Input

There will be T (T <= 25) test cases in the input file. First line of the input contains two positive integers, N (N <= 100,000) and Q (Q <= 100,000). 
The next line contains N integers, each at most 1000. Each of the next Q lines starts with a number, which indicates the type of operation:

2 st nd -- return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1 <= st <= nd <= N).

1 st nd x -- add "x" to all numbers with indices in [st, nd] (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).

0 st nd x -- set all numbers with indices in [st, nd] to "x" (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).

Output

For each test case output the “Case <caseno>:” in the first line and from the second line output the sum of squares for each operation of type 2. Intermediate overflow will not occur with proper use of 64-bit signed integer.

Input:

Output:

Case 1:
30
7
13
Case 2:
1

class Main {
    static class TreeNode {
        int sum, sq_sum;

        TreeNode(int sum, int sq_sum) {
            this.sum = sum;
            this.sq_sum = sq_sum;
        }
    }

    static class LazyNode {
        // type : 0-> shows that no action is needed , 1-> shows that increment is needed,
        // 2-> replacement is needed
        int type, value;

        LazyNode(int type, int value) {
            this.type = type;
            this.value = value;
        }
    }

    public static void helper(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index) {
        if (lazy[index].type == 1) {
            tree[index].sq_sum += (lazy[index].value * lazy[index].value * (end - start + 1))
                    + (2 * lazy[index].value * tree[index].sum);
            tree[index].sum += lazy[index].value * (end - start + 1);
            if (start != end) {
                lazy[2 * index] = new LazyNode(1, lazy[2 * index].value + lazy[index].value);
                lazy[2 * index + 1] = new LazyNode(1, lazy[2 * index + 1].value + lazy[index].value);
            }
        } else {
            tree[index].sq_sum = (end - start + 1) * lazy[index].value * lazy[index].value;
            tree[index].sum = (end - start + 1) * lazy[index].value;
            if (start != end) {
                lazy[2 * index] = new LazyNode(2, lazy[index].value);
                lazy[2 * index + 1] = new LazyNode(2, lazy[index].value);
            }
        }
        lazy[index] = new LazyNode(0, 0);
    }

    // building the lazy tree aswell with its default values
    public static void build(int[] arr, TreeNode[] tree, LazyNode[] lazy, int start, int end, int index) {
        if (start == end) {
            tree[index] = new TreeNode(arr[start], arr[start] * arr[start]);
            lazy[index] = new LazyNode(0, 0); // default values
            return;
        }
        int mid = (start + end) / 2;
        build(arr, tree, lazy, start, mid, 2 * index);
        build(arr, tree, lazy, mid + 1, end, 2 * index + 1);
        tree[index] = new TreeNode(tree[2 * index].sum + tree[2 * index + 1].sum,
                tree[2 * index].sq_sum + tree[2 * index + 1].sq_sum);
        lazy[index] = new LazyNode(0, 0);// default values
    }

    public static void update(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index, int L, int R, int value,
            int type) {
        if (lazy[index].type != 0)
            helper(tree, lazy, start, end, index);
        // no overlap
        if (start > R || end < L)
            return;
        // complete overlap
        if (start >= L && end <= R) {
            if (type == 1) {
                tree[index].sq_sum += 2 * value * tree[index].sum + (value * value * (end - start + 1));
                tree[index].sum += value * (end - start + 1);
                if (start != end) {
                    lazy[2 * index] = new LazyNode(1, lazy[2 * index].value + value);
                    lazy[2 * index + 1] = new LazyNode(1, lazy[2 * index + 1].value + value);
                }
            } else {
                tree[index].sq_sum = value * value * (end - start + 1);
                tree[index].sum = value * (end - start + 1);
                if (start != end) {
                    lazy[2 * index] = new LazyNode(2, value);
                    lazy[2 * index + 1] = new LazyNode(2, value);
                }
            }
            return;
        }
        // partial overlap
        int mid = (start + end) / 2;
        update(tree, lazy, start, mid, 2 * index, L, R, value, type);
        update(tree, lazy, mid + 1, end, 2 * index + 1, L, R, value, type);
        tree[index].sq_sum = tree[2 * index].sq_sum + tree[2 * index + 1].sq_sum;
        tree[index].sum = tree[2 * index].sum + tree[2 * index + 1].sum;
    }

    public static TreeNode printQuery(TreeNode[] tree, LazyNode[] lazy, int start, int end, int index, int l, int r) {
        // no overlap
        if (start > r || end < l)
            return new TreeNode(0, 0);
        if (lazy[index].type != 0)
            helper(tree, lazy, start, end, index);
        // complete overlap
        if (start >= l && end <= r)
            return tree[index];
        // partial overlap
        int mid = (start + end) / 2;
        TreeNode leftAns = printQuery(tree, lazy, start, mid, 2 * index, l, r);
        TreeNode rightAns = printQuery(tree, lazy, mid + 1, end, 2 * index + 1, l, r);
        return new TreeNode(leftAns.sum + rightAns.sum, leftAns.sq_sum + rightAns.sq_sum);
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        for (int j = 1; j <= t; j++) {
            int n = s.nextInt(), q = s.nextInt();
            int arr[] = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = s.nextInt();
            TreeNode[] tree = new TreeNode[4 * n];
            LazyNode[] lazy = new LazyNode[4 * n];
            build(arr, tree, lazy, 0, n - 1, 1);
            System.out.println("Case " + j + ":");
            while (q-- > 0) {
                int type = s.nextInt();
                int st = s.nextInt() - 1;
                int nd = s.nextInt() - 1;
                if (type == 2)
                    System.out.println(printQuery(tree, lazy, 0, n - 1, 1, st, nd).sq_sum);
                else {
                    int x = s.nextInt();
                    if (type == 1)
                        update(tree, lazy, 0, n - 1, 1, st, nd, x, 1);
                    else
                        update(tree, lazy, 0, n - 1, 1, st, nd, x, 2);
                }
            }
        }
        s.close();
    }
}

Question - 6

The fight for the best number in the globe is going to finally come to an end.The top two contenders for the best number are number 2 and number 3.It's the final the entire world was waiting for. Expectorates from all across the globe came to witness the breath taking finals.

The finals began in an astonishing way.A common problem was set for both of them which included both these number.The problem goes like this.

Given a binary string (that is a string consisting of only 0 and 1). They were supposed to perform two types of query on the string.

Type 0: Given two indices l and r.Print the value of the binary string from l to r modulo 3.

Type 1: Given an index l flip the value of that index if and only if the value at that index is 0.

The problem proved to be a really tough one for both of them.Hours passed by but neither of them could solve the problem.So both of them wants you to solve this problem and then you get the right to choose the best number in the globe.

Input:

The first line contains N denoting the length of the binary string .
The second line contains the N length binary string.Third line contains the integer Q indicating the number of queries to perform.
This is followed up by Q lines where each line contains a query.

Output:

For each query of Type 0 print the value modulo 3.

Constraints:

1<= N <=10^5

1<= Q <= 10^5

0 <= l <= r < N

Sample Input

Sample Output

public class Main {
    static int[] power = new int[100006], arr = new int[100006], tree = new int[300000];

    public static void calculatePowers() {
        power[0] = 1;
        for (int i = 1; i < 100006; i++)
            power[i] = (power[i - 1] * 2) % 3;
    }

    public static void build(int index, int start, int end) {
        if (start == end)
            tree[index] = arr[start];
        else {
            int mid = start + (end - start) / 2;
            build(2 * index, start, mid);
            build(2 * index + 1, mid + 1, end);
            tree[index] = (tree[2 * index] * power[end - mid] + tree[2 * index + 1]) % 3;
        }
    }

    public static int query(int index, int start, int end, int L, int R) {
        if (R < start || L > end)
            return 0;
        if (L <= start && end <= R)
            return (tree[index] * power[R - end]) % 3;
        int mid = (start + end) / 2;
        int p1 = query(2 * index, start, mid, L, R);
        int p2 = query(2 * index + 1, mid + 1, end, L, R);
        return (p1 + p2) % 3;
    }

    public static void update(int index, int start, int end, int idx) {
        if (start == end) {
            tree[index] = 1;
            arr[idx] = 1;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && mid >= idx)
                update(2 * index, start, mid, idx);
            else
                update(2 * index + 1, mid + 1, end, idx);
            tree[index] = (tree[2 * index] * power[end - mid] % 3) + tree[2 * index + 1] % 3;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        char[] str = in.nextLine().toCharArray();
        calculatePowers();
        for (int i = 0; i < n; i++)
            arr[i + 1] = str[i] - '0';
        build(1, 1, n);
        int q = in.nextInt();
        while (q-- > 0) {
            int t = in.nextInt();
            if (t == 0) {
                int l = in.nextInt(), r = in.nextInt();
                System.out.println(query(1, 1, n, l + 1, r + 1));
            } else {
                int x = in.nextInt();
                if (str[x] == '0') {
                    str[x] = '1';
                    arr[x + 1] = 1;
                    update(1, 1, n, x + 1);
                }
            }
        }
    }
}

Question - 7

World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array of N elements, which are initially all 0. After that you will be given C commands. They are -

0 p q v - you have to add v to all numbers in the range of p to q (inclusive), where p and q are two indexes of the array.

1 p q - output a line containing a single integer which is the sum of all the array elements between p and q (inclusive)

Input

In the first line you'll be given T, number of test cases.

Each test case will start with N (N <= 100 000) and C (C <= 100 000). After that you'll be given C commands in the format as mentioned above. 1 <= p, q <= N and 1 <= v <= 10^7.

Output

Print the answers of the queries.

Input:

Output:

80  
508

public class Main {
    public static void update(long[] tree, long[] lazy, int start, int end, int index, int l, int r, long value) {
        if (lazy[index] != 0) {
            tree[index] += lazy[index] * (end - start + 1);
            if (start != end) {
                lazy[2 * index] += lazy[index];
                lazy[2 * index + 1] += lazy[index];
            }
            lazy[index] = 0;
        }
        // no overlap
        if (start > r || end < l)
            return;
        // complete overlap
        if (start >= l && end <= r) {
            tree[index] += value * (end - start + 1);
            if (start != end) {
                lazy[2 * index] += value;
                lazy[2 * index + 1] += value;
            }
            return;
        }
        // partial overlap
        int mid = (start + end) / 2;
        update(tree, lazy, start, mid, 2 * index, l, r, value);
        update(tree, lazy, mid + 1, end, 2 * index + 1, l, r, value);
        tree[index] = tree[2 * index] + tree[2 * index + 1];
    }

    public static long printQuery(long[] tree, long[] lazy, int start, int end, int index, int l, int r) {
        // no overlap
        if (start > r || end < l) 
            return 0;
        if (lazy[index] != 0) {
            tree[index] += lazy[index] * (end - start + 1);
            if (start != end) {
                lazy[2 * index] += lazy[index];
                lazy[2 * index + 1] += lazy[index];
            }
            lazy[index] = 0;
        }
        // complete overlap
        if (start >= l && end <= r)
            return tree[index];
        // partial overlap
        int mid = (start + end) / 2;
        long ans1 = printQuery(tree, lazy, start, mid, 2 * index, l, r);
        long ans2 = printQuery(tree, lazy, mid + 1, end, 2 * index + 1, l, r);
        long temp = ans1 + ans2;
        return temp;

    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while (t-- > 0) {
            int n = s.nextInt();
            long tree[] = new long[4 * n];
            long lazy[] = new long[4 * n];
            // no need to build seprately as all the values are going to be 0 in the
            // starting
            int c = s.nextInt();
            while (c-- > 0) {
                int type = s.nextInt();
                if (type == 0) {
                    int p = s.nextInt() - 1;
                    int q = s.nextInt() - 1;
                    long v = s.nextInt();
                    update(tree, lazy, 0, n - 1, 1, p, q, v);
                } else {
                    int p = s.nextInt() - 1;
                    int q = s.nextInt() - 1;
                    System.out.println(printQuery(tree, lazy, 0, n - 1, 1, p, q));
                }
            }
        }
    }
}

Question - 8

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

class MajorityChecker {
    // A treeNode stores the majority element, with it's count
    // for a given range
    static class Pair {
        int element, count;

        Pair(int element, int count) {
            this.element = element;
            this.count = count;
        }
    }

    int[] arr;
    Pair[] tree;
    // Map of Elements -> TreeSet of their indices
    // This is used for finding the occourence of an element in a given range in O(logN)
    Map<Integer, TreeSet<int[]>> map = new HashMap<>();

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        tree = new Pair[4 * arr.length];
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], k -> new TreeSet<>((a, b) -> a[0] - b[0]));
            map.get(arr[i]).add(new int[] { i, map.get(arr[i]).size() });
        }
        // NlogN process
        buildTree(0, arr.length - 1, 1);
    }

    public void buildTree(int start, int end, int index) {
        if (start == end) {
            tree[index] = new Pair(arr[start], 1);
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(start, mid, 2 * index);
        buildTree(mid + 1, end, 2 * index + 1);
        Pair left = tree[2 * index], right = tree[2 * index + 1];
        int leftCount = 0, rightCount = 0;
        if (left.element != -1)
            leftCount = map.get(left.element).floor(new int[] { end, 0 })[1]
                    - map.get(left.element).ceiling(new int[] { start, 0 })[1] + 1;
        if (right.element != -1)
            rightCount = map.get(right.element).floor(new int[] { end, 0 })[1]
                    - map.get(right.element).ceiling(new int[] { start, 0 })[1] + 1;
        if (leftCount * 2 > end - start + 1)
            tree[index] = new Pair(left.element, leftCount);
        else if (rightCount * 2 > end - start + 1)
            tree[index] = new Pair(right.element, rightCount);
        else
            tree[index] = new Pair(-1, 0);
    }

    public int query(int left, int right, int threshold) {
        // LogN*LogN
        Pair majority = findMajority(0, arr.length - 1, 1, left, right);
        if (majority.count >= threshold)
            return majority.element;
        return -1;
    }

    public Pair findMajority(int start, int end, int index, int L, int R) {
        if (start > R || end < L)
            return new Pair(-1, 0);
        if (start >= L && end <= R)
            return tree[index];
        int mid = start + (end - start) / 2;
        Pair left = findMajority(start, mid, 2 * index, L, R);
        Pair right = findMajority(mid + 1, end, 2 * index + 1, L, R);
        Pair ans = new Pair(-1, 0);
        int leftCount = 0, rightCount = 0;
        int limit1 = Math.max(L, start), limit2 = Math.min(R, end);
        if (left.element != -1)
            leftCount = map.get(left.element).floor(new int[] { limit2, 0 })[1]
                    - map.get(left.element).ceiling(new int[] { limit1, 0 })[1] + 1;
        if (right.element != -1)
            rightCount = map.get(right.element).floor(new int[] { limit2, 0 })[1]
                    - map.get(right.element).ceiling(new int[] { limit1, 0 })[1] + 1;
        if (leftCount * 2 > limit2 - limit1 + 1)
            ans = new Pair(left.element, leftCount);
        else if (rightCount * 2 > limit2 - limit1 + 1)
            ans = new Pair(right.element, rightCount);
        return ans;
    }
}

Question - 9

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

Constraints:

1 <= num.length <= 30000
num contains digits only and doesn't have leading zeros.
1 <= k <= 10^9

class Solution {
    public String minInteger(String num, int k) {
        // list stores the location of each digit.
        List<Queue<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= 9; ++i)
            list.add(new LinkedList<>());
        for (int i = 0; i < num.length(); ++i)
            list.get(num.charAt(i) - '0').add(i);
        String ans = "";
        SegmentTree seg = new SegmentTree(num.length());
        for (int i = 0; i < num.length(); ++i) {
            // At each location, try to place 0....9
            for (int digit = 0; digit <= 9; ++digit) {
                // is there any occurrence of digit left?
                if (list.get(digit).size() != 0) {
                    // yes, there is a occurrence of digit at pos
                    Integer pos = list.get(digit).peek();
                    // Since few numbers already shifted to left, this `pos` might be outdated.
                    // we try to find how many number already got shifted that were to the left of
                    // pos.
                    int shift = seg.getCountLessThan(pos);
                    // (pos - shift) is number of steps to make digit move from pos to i.
                    if (pos - shift <= k) {
                        k -= pos - shift;
                        // Add pos to our segment tree.
                        seg.add(pos);
                        list.get(digit).remove();
                        ans += digit;
                        break;
                    }
                }
            }
        }
        return ans;
    }

    class SegmentTree {
        int[] nodes;
        int n;

        // Segment tree only stores the indices of shifted elements
        public SegmentTree(int max) {
            nodes = new int[4 * (max)];
            n = max;
        }

        public void add(int num) {
            addUtil(num, 0, n, 1);
        }

        private void addUtil(int num, int start, int end, int index) {
            if (num < start || num > end)
                return;
            if (start == end) {
                nodes[index]++;
                return;
            }
            int mid = (start + end) / 2;
            addUtil(num, start, mid, 2 * index);
            addUtil(num, mid + 1, end, 2 * index + 1);
            nodes[index] = nodes[2 * index] + nodes[2 * index + 1];
        }

        // Essentialy it tells number of shifted numbers < num.
        public int getCountLessThan(int num) {
            return getUtil(0, num, 0, n, 1);
        }

        private int getUtil(int leftLimit, int rightLimit, int start, int end, int index) {
            // No overlap
            if (rightLimit < start || leftLimit > end)
                return 0;
            // Full overlap
            if (leftLimit <= start && rightLimit >= end)
                return nodes[index];
            // Partial overlap
            int mid = (start + end) / 2;
            return getUtil(leftLimit, rightLimit, start, mid, 2 * index)
                    + getUtil(leftLimit, rightLimit, mid + 1, end, 2 * index + 1);
        }
    }
}

PreviousMerge Sort

Last updated 4 years ago