Process prefix queries in a binary string efficiently

Given an binary string S (contains '0' or '1' only), we need to process 2 type of queries as following:

1. 1 K V : Update the value of Kth index in the string with value V(can only be 0/1 character).
2. 2 L R : Print the value of Fun(L, R): for substring X = S[L: R] and we take the prefix Y = S[0: R - L] and count the num of positions for which X[i] != Y[j], for i = [L, R], j = [0, R - L].

Constraints :

N (length of S)      <= 10 ^ 5
Q (number of query ) <= 10 ^ 5

Sample test case:

S = "111101"
Query(2 3 5) = 1

Explanation :

Here, X = '101' and Y = '111', only X[1] != Y[1], rest all bits are positionally same.

Approach:

public List<Integer> solve(StringBuffer S, int[][] q) {
   int N = S.length();
   int Q = q.length();

   List<Integer> result = new ArrayList<>();
   for(int i = 0; i < Q; i++) {
      
      if(Q[i][0] == 1) // type-1
         S.setCharAt(Q[i][1], Q[i][2]);

      else if(Q[i][0] == 2) { // type-2

         int L = Q[i][1];
         int R = Q[i][2];
         int count = 0;
         for(int i = 0; i < R - L + 1; i++, L++) {
            if(S.charAt(i) != S.charAt(L))
               count += 1;
         }

         result.add(count);
      }
   }


   return result;
}

Time Complexity : O(Q * N)

How can we solve this problem more efficiently, such that the time complexity for each query would be less that O(N).