线段树模板

class Solution {
    boolean[] todo; // 懒标记
    int[] cnt1;     // 要维护的值
    public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        todo = new boolean[n * 4]; // 划分的子区间个数不超过4n
        cnt1 = new int[n * 4];
        build(1, 1, n, nums1);
        var sum = 0L;
        for (var x : nums2)
            sum += x;
        List<Long> ans = new ArrayList<>();
        for(int[] query: queries){
            if(query[0] == 1){
                update(1, 1, n, query[1] + 1, query[2] + 1);
            }else if(query[0] == 2){
                sum += (long) cnt1[1] * query[1];
            }else{
                ans.add(sum);
            }
        }
        long[] ans2 = new long[ans.size()];
        for(int i = 0; i < ans2.length; ++i){
            ans2[i] = ans.get(i);
        }
        return ans2;
    }
    // 初始化线段树 O(n)
    public void build(int idx, int l, int r, int[] nums1){
        // 到达叶子节点
        if(l == r){
            cnt1[idx] = nums1[l - 1];
            return;
        }
        int m = (l + r) / 2;
        // 递归左子树和右子树
        build(idx * 2, l, m, nums1);
        build(idx * 2 + 1, m + 1, r, nums1);
        // 根据左子树和右子树维护当前节点
        cnt1[idx] = cnt1[idx * 2] + cnt1[idx * 2 + 1];
    }

    // 利用懒标记更新[l,r]区间
    public void mydo(int idx, int l, int r){
        cnt1[idx] = r - l + 1 - cnt1[idx];
        todo[idx] = !todo[idx];
    }

    // 更新[L,R]区间的线段树 O(n)
    public void update(int idx, int l, int r, int L, int R){
        if(l >= L && r <= R){
            // 更新[l,r]区间
            mydo(idx, l, r);
            return;
        }
        int m = (l + r) / 2;
        // 将当前懒标记传递给左子树和右子树
        if(todo[idx]){
            mydo(idx * 2, l, m);
            mydo(idx * 2 + 1, m + 1, r);
            todo[idx] = false;
        }
        // 更新左子树和右子树
        if(m >= L){
            update(idx * 2, l, m, L, R);
        }
        if(m < R){
            update(idx * 2 + 1, m + 1, r, L, R);
        }
        // 利用左子树和右子树的结果更新当前节点
        cnt1[idx] = cnt1[idx * 2] + cnt1[idx * 2 + 1];
    }
}