CSES静态区间和查询稀疏表实现运行时错误及数组大小咨询

• 稀疏表第一维容量不足：当前定义的st数组第一维只有100000，而题目允许数组长度最高为200000，当n超过100000时，向st[i][0]赋值的操作会触发数组越界，这是最直接的运行时错误原因。
• k值设置偏小：2^17=131072，小于200000，无法覆盖最长的区间长度，会导致长区间的查询结果错误。
• 稀疏表构建逻辑不完整：构建表时循环条件为j<k，但查询时遍历到j=k，对应层级的st值没有被初始化，也会触发异常。
• 冗余大内存申请：局部数组a开了10000000的长度，完全超出需求，会不必要占用大量内存，存在内存溢出风险。
• 变量重复定义：全局已经定义了static int n，main方法中又重新定义了局部变量int n，属于不规范写法。

针对题目最高200000的数组长度：

• 第一维：设置为200005即可，比最大长度多预留少量空间避免边界越界
• 第二维：k值取18即可，因为2^18=262144 ≥ 200000，所以第二维长度为k+1=19
  最终st的定义应为：static long st[][] = new long[200005][19];，同时把k的取值改为18。

class Mai{
    static int n;
    static int k = 18;
    static long st[][] = new long[200005][k+1];
    public static void main(String[] args) throws IOException {
        Reader sc = new Reader();
        n = sc.nextInt(); // 直接给全局变量赋值，不要重复定义
        long q = sc.nextLong();
        long a[] = new long[200005]; // 调整数组a的大小
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            st[i][0] = a[i];
        }
        // 调整循环条件为j<=k，确保所有层级都被初始化
        for(int j=1;j<=k;j++){
            for(int i=0;i+(1<<j)<=n;i++){
                st[i][j] = st[i][j-1] + st[i + (1 << (j - 1))][j - 1];
            }
        }
        while(q-->0){
            int l= sc.nextInt();
            int r =sc.nextInt();
            l--;
            r--;
            query(l,r);
        }
    }

    public static void query(int l,int r){
        long sum=0;
        for(int j=k;j>=0;j--){
            if((1<<j) <= (r-l+1)){
                sum += st[l][j];
                l += 1<<j;
            }
        }
        System.out.println(sum);
    }  
}

内容的提问来源于stack exchange，提问作者Abhishek Raj