高效处理二进制字符串中的前缀查询

Question

给定一个二进制字符串 S （仅包含“0”或“1”），我们需要处理以下 2 种类型的查询：

1. 1 K V ：更新 < 的值code>Kth 字符串中值为 V 的索引（只能是 0/1 个字符）。
2. 2 L R ：打印 Fun(L, R) 的值：对于子字符串 X = S[L: R]，我们采用前缀Y = S[0: R - L] 并计算 X[i] != Y[j] 的位置数量，其中 i = [L, R ]，j = [0，R - L]。

约束：

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

示例测试用例：

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

说明：

此处，X = '101' 且 Y = '111'，仅 X[1 ] != Y[1]，其余所有位位置相同。

方法：

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;
}

时间复杂度：O(Q * N)

我们怎样才能更有效地解决这个问题，使得每个查询的时间复杂度小于O(N)。