Power of 3

Given a binary string A of size N and an integer matrix B of size Q x 3.

Matrix B had Q queries:

Note: Rows are numbered from top to bottom and columns are numbered from left to right.

The first argument given is the string A.
The second argument given is the integer matrix B.

Return an array of size Q where ith value is answer to ith query.

1 <= N <= 100000
1 <= Q <= 200000
1 <= B[i][1], B[i][2] <= N
B[i][1] <= B[i][2]

Input 1:
    A = 10010
    B = [ [0, 3, 5]
          [0, 3, 4]
          [1, 2, -1]
          [0, 1, 5]
          [1, 2, -1]
          [0, 1, 4] ]
Output 1:
    [2, 1, -1, 2, -1, 1]

Solution:

public class Solution {
    static class SegTree {
        private int[] arr;

        public SegTree(int n) {
            arr = new int[4 * n];
        }
        
        public void build(String A) {
            build(A, 1, 1, A.length());
        }
        
        public int query(int root, int start, int end, int qStart, int qEnd) {
            // System.out.println("start: " + start + " end: " + end + " qStart: " + qStart + " qEnd: " + qEnd);
            if (start == qStart && end == qEnd) {
                return arr[root];
            }
            int mid = start + (end - start) / 2;
            if (qEnd <= mid) {
                return query(left(root), start, mid, qStart, qEnd);
            } else if (qStart <= mid && mid <= qEnd) {
                int left = query(left(root), start, mid, qStart, mid);
                int right = query(right(root), mid + 1, end, mid + 1, qEnd);
                if ((qEnd - mid) % 2 == 0) {
                    return (left + right) % 3;
                } else {
                    return (3 - left + right) % 3;
                }
            } else {
                return query(right(root), mid + 1, end, qStart, qEnd);
            }
        }
        
        public void update(int root, int start, int end, int index) {
            if (start == index && end == index) {
                arr[root] = 1; 
                return;
            }
            int mid = start + (end - start) / 2;
            if (index <= mid) {
                update(left(root), start, mid, index);
            } else {
                update(right(root), mid + 1, end, index);
            }
            if ((end - mid) % 2 == 0) {
                arr[root] = (arr[left(root)] + arr[right(root)]) % 3;
            } else {
                arr[root] = (3 - arr[left(root)] + arr[right(root)]) % 3;
            }
        }
        
        private void build(String A, int root, int start, int end) {
            if (start == end) {
                arr[root] = A.charAt(start - 1) - '0';
                return;
            }
            int mid = start + (end - start) / 2;
            build(A, left(root), start, mid);
            build(A, right(root), mid + 1, end);
            if ((end - mid) % 2 == 0) {
                arr[root] = (arr[left(root)] + arr[right(root)]) % 3;
            } else {
                arr[root] = (3 - arr[left(root)] + arr[right(root)]) % 3;
            }
        }
        
        private int left(int root) {
            return 2 * root;
        }
        
        private int right(int root) {
            return 2 * root + 1;
        }
    }
    
    public ArrayList<Integer> solve(String A, ArrayList<ArrayList<Integer>> B) {
        int n = A.length();
        SegTree tree = new SegTree(n);
        tree.build(A);
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < B.size(); i ++) {
            ArrayList<Integer> query = B.get(i);
            if (query.get(0) == 0) {
                result.add(tree.query(1, 1, n, query.get(1), query.get(2)));
            } else {
                tree.update(1, 1, n, query.get(1));
                result.add(-1);
            }
        }
        return result;
    }
}