// 线段树模版
    class SegmentTree {
        private int[] tree;          // 线段树数组
        private int[] lazy;          // 懒加载数组
        private int n;               // 原始数组长度
        private static final int DEFAULT = 0;  // 默认值，根据需求修改

        /**
         * 构造函数
         * @param arr 初始化线段树的数组
         */
        public SegmentTree(int[] arr) {
            n = arr.length;
            tree = new int[4 * n];   // 4*n的大小足以容纳线段树
            lazy = new int[4 * n];
            build(arr, 0, n - 1, 0);
        }

        /**
         * 构建线段树
         * @param arr 原始数组
         * @param start 原始数组起始索引
         * @param end 原始数组结束索引
         * @param node 当前节点索引
         */
        private void build(int[] arr, int start, int end, int node) {
            // 叶子节点
            if (start == end) {
                tree[node] = arr[start];
                return;
            }

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归构建左右子树
            build(arr, start, mid, leftChild);
            build(arr, mid + 1, end, rightChild);

            // 合并左右子树的结果（此处为求和，可根据需求修改）
            tree[node] = merge(tree[leftChild], tree[rightChild]);
        }

        /**
         * 合并两个节点的值
         * 此处实现为求和，可根据需求修改为求最大值、最小值等
         * @param a 左节点值
         * @param b 右节点值
         * @return 合并后的值
         */
        private int merge(int a, int b) {
            return a + b;
        }

        /**
         * 懒加载 propagation
         * 将当前节点的更新推送到子节点
         * @param node 当前节点索引
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         */
        private void pushDown(int node, int start, int end) {
            // 如果没有懒加载值，直接返回
            if (lazy[node] == DEFAULT) {
                return;
            }

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 更新左子树
            tree[leftChild] += lazy[node] * (mid - start + 1);  // 此处为区间加法，可根据需求修改
            lazy[leftChild] += lazy[node];

            // 更新右子树
            tree[rightChild] += lazy[node] * (end - mid);        // 此处为区间加法，可根据需求修改
            lazy[rightChild] += lazy[node];

            // 清除当前节点的懒加载值
            lazy[node] = DEFAULT;
        }

        /**
         * 区间更新
         * @param l 要更新的区间起始索引
         * @param r 要更新的区间结束索引
         * @param val 要更新的值（此处为加法，可根据需求修改）
         */
        public void updateRange(int l, int r, int val) {
            updateRange(0, n - 1, l, r, val, 0);
        }

        /**
         * 区间更新的递归实现
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         * @param l 要更新的区间起始索引
         * @param r 要更新的区间结束索引
         * @param val 要更新的值
         * @param node 当前节点索引
         */
        private void updateRange(int start, int end, int l, int r, int val, int node) {
            // 当前节点覆盖范围与要更新的范围无交集
            if (start > r || end < l) {
                return;
            }

            // 当前节点覆盖范围完全在要更新的范围内
            if (start >= l && end <= r) {
                // 更新当前节点的值（此处为加法，可根据需求修改）
                tree[node] += val * (end - start + 1);
                // 如果不是叶子节点，更新懒加载值
                if (start != end) {
                    lazy[node] += val;
                }
                return;
            }

            // 推送懒加载值到子节点
            pushDown(node, start, end);

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归更新左右子树
            updateRange(start, mid, l, r, val, leftChild);
            updateRange(mid + 1, end, l, r, val, rightChild);

            // 合并左右子树的结果
            tree[node] = merge(tree[leftChild], tree[rightChild]);
        }

        /**
         * 单点更新
         * @param index 要更新的索引
         * @param val 新值（此处为设置为新值，可根据需求修改为加法等）
         */
        public void updatePoint(int index, int val) {
            // 计算需要增加的值（从当前值变为val）
            int current = queryPoint(index);
            updateRange(index, index, val - current);
        }

        /**
         * 查询单点值
         * @param index 要查询的索引
         * @return 索引处的值
         */
        public int queryPoint(int index) {
            return queryRange(index, index);
        }

        /**
         * 区间查询
         * @param l 要查询的区间起始索引
         * @param r 要查询的区间结束索引
         * @return 查询结果（此处为区间和，可根据需求修改）
         */
        public int queryRange(int l, int r) {
            return queryRange(0, n - 1, l, r, 0);
        }

        /**
         * 区间查询的递归实现
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         * @param l 要查询的区间起始索引
         * @param r 要查询的区间结束索引
         * @param node 当前节点索引
         * @return 查询结果
         */
        private int queryRange(int start, int end, int l, int r, int node) {
            // 当前节点覆盖范围与要查询的范围无交集
            if (start > r || end < l) {
                return DEFAULT;
            }

            // 当前节点覆盖范围完全在要查询的范围内
            if (start >= l && end <= r) {
                return tree[node];
            }

            // 推送懒加载值到子节点
            pushDown(node, start, end);

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归查询左右子树
            int leftSum = queryRange(start, mid, l, r, leftChild);
            int rightSum = queryRange(mid + 1, end, l, r, rightChild);

            // 合并查询结果
            return merge(leftSum, rightSum);
        }

        /**
         * 打印线段树结构（用于调试）
         */
        public void printTree() {
            System.out.println("线段树数组: " + Arrays.toString(tree));
            System.out.println("懒加载数组: " + Arrays.toString(lazy));
        }
    }

求和

// 线段树模版 (求和)
    class SegmentTree {
        private int[] tree;          // 线段树数组
        private int[] lazy;          // 懒加载数组
        private int n;               // 原始数组长度
        private static final int DEFAULT = 0;  // 默认值，根据需求修改

        /**
         * 构造函数
         * @param arr 初始化线段树的数组
         */
        public SegmentTree(int[] arr) {
            n = arr.length;
            tree = new int[4 * n];   // 4*n的大小足以容纳线段树
            lazy = new int[4 * n];
            build(arr, 0, n - 1, 0);
        }

        /**
         * 构建线段树
         * @param arr 原始数组
         * @param start 原始数组起始索引
         * @param end 原始数组结束索引
         * @param node 当前节点索引
         */
        private void build(int[] arr, int start, int end, int node) {
            // 叶子节点
            if (start == end) {
                tree[node] = arr[start];
                return;
            }

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归构建左右子树
            build(arr, start, mid, leftChild);
            build(arr, mid + 1, end, rightChild);

            // 合并左右子树的结果（此处为求和，可根据需求修改）
            tree[node] = merge(tree[leftChild], tree[rightChild]);
        }

        /**
         * 合并两个节点的值
         * 此处实现为求和，可根据需求修改为求最大值、最小值等
         * @param a 左节点值
         * @param b 右节点值
         * @return 合并后的值
         */
        private int merge(int a, int b) {
            return a + b;
        }

        /**
         * 懒加载 propagation
         * 将当前节点的更新推送到子节点
         * @param node 当前节点索引
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         */
        private void pushDown(int node, int start, int end) {
            // 如果没有懒加载值，直接返回
            if (lazy[node] == DEFAULT) {
                return;
            }

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 更新左子树
            tree[leftChild] += lazy[node] * (mid - start + 1);  // 此处为区间加法，可根据需求修改
            lazy[leftChild] += lazy[node];

            // 更新右子树
            tree[rightChild] += lazy[node] * (end - mid);        // 此处为区间加法，可根据需求修改
            lazy[rightChild] += lazy[node];

            // 清除当前节点的懒加载值
            lazy[node] = DEFAULT;
        }

        /**
         * 区间更新
         * @param l 要更新的区间起始索引
         * @param r 要更新的区间结束索引
         * @param val 要更新的值（此处为加法，可根据需求修改）
         */
        public void updateRange(int l, int r, int val) {
            updateRange(0, n - 1, l, r, val, 0);
        }

        /**
         * 区间更新的递归实现
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         * @param l 要更新的区间起始索引
         * @param r 要更新的区间结束索引
         * @param val 要更新的值
         * @param node 当前节点索引
         */
        private void updateRange(int start, int end, int l, int r, int val, int node) {
            // 当前节点覆盖范围与要更新的范围无交集
            if (start > r || end < l) {
                return;
            }

            // 当前节点覆盖范围完全在要更新的范围内
            if (start >= l && end <= r) {
                // 更新当前节点的值（此处为加法，可根据需求修改）
                tree[node] += val * (end - start + 1);
                // 如果不是叶子节点，更新懒加载值
                if (start != end) {
                    lazy[node] += val;
                }
                return;
            }

            // 推送懒加载值到子节点
            pushDown(node, start, end);

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归更新左右子树
            updateRange(start, mid, l, r, val, leftChild);
            updateRange(mid + 1, end, l, r, val, rightChild);

            // 合并左右子树的结果
            tree[node] = merge(tree[leftChild], tree[rightChild]);
        }

        /**
         * 单点更新
         * @param index 要更新的索引
         * @param val 新值（此处为设置为新值，可根据需求修改为加法等）
         */
        public void updatePoint(int index, int val) {
            // 计算需要增加的值（从当前值变为val）
            int current = queryPoint(index);
            updateRange(index, index, val - current);
        }

        /**
         * 查询单点值
         * @param index 要查询的索引
         * @return 索引处的值
         */
        public int queryPoint(int index) {
            return queryRange(index, index);
        }

        /**
         * 区间查询
         * @param l 要查询的区间起始索引
         * @param r 要查询的区间结束索引
         * @return 查询结果（此处为区间和，可根据需求修改）
         */
        public int queryRange(int l, int r) {
            return queryRange(0, n - 1, l, r, 0);
        }

        /**
         * 区间查询的递归实现
         * @param start 当前节点覆盖的起始索引
         * @param end 当前节点覆盖的结束索引
         * @param l 要查询的区间起始索引
         * @param r 要查询的区间结束索引
         * @param node 当前节点索引
         * @return 查询结果
         */
        private int queryRange(int start, int end, int l, int r, int node) {
            // 当前节点覆盖范围与要查询的范围无交集
            if (start > r || end < l) {
                return DEFAULT;
            }

            // 当前节点覆盖范围完全在要查询的范围内
            if (start >= l && end <= r) {
                return tree[node];
            }

            // 推送懒加载值到子节点
            pushDown(node, start, end);

            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            // 递归查询左右子树
            int leftSum = queryRange(start, mid, l, r, leftChild);
            int rightSum = queryRange(mid + 1, end, l, r, rightChild);

            // 合并查询结果
            return merge(leftSum, rightSum);
        }

        /**
         * 打印线段树结构（用于调试）
         */
        public void printTree() {
            System.out.println("线段树数组: " + Arrays.toString(tree));
            System.out.println("懒加载数组: " + Arrays.toString(lazy));
        }
    }

求积

// 线段树模版 (求积)
class SegmentTreeProduct {

    // 线段树数组，存储区间乘积
    private long[] tree;
    // 原始数据数组
    private long[] data;
    // 数据长度
    private int n;

    // 构造函数，初始化线段树
    public SegmentTreeProduct(long[] arr) {
        n = arr.length;
        data = new long[n];
        System.arraycopy(arr, 0, data, 0, n);
        // 线段树大小通常取 4*n 确保足够
        tree = new long[4 * n];
        build(0, 0, n - 1);
    }

    // 构建线段树
    private void build(int node, int start, int end) {
        if (start == end) {
            // 叶子节点，存储单个元素值
            tree[node] = data[start];
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            // 递归构建左子树
            build(leftChild, start, mid);
            // 递归构建右子树
            build(rightChild, mid + 1, end);
            // 当前节点值为左右子树乘积
            tree[node] = tree[leftChild] * tree[rightChild];
        }
    }

    // 单点更新：将 index 位置的值更新为 val
    public void update(int index, int val) {
        if (index < 0 || index >= n) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        data[index] = val;
        update(0, 0, n - 1, index, val);
    }

    // 递归实现单点更新
    private void update(int node, int start, int end, int index, int val) {
        if (start == end) {
            // 找到目标位置，更新值
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            if (index <= mid) {
                // 目标位置在左子树，更新左子树
                update(leftChild, start, mid, index, val);
            } else {
                // 目标位置在右子树，更新右子树
                update(rightChild, mid + 1, end, index, val);
            }
            // 更新当前节点值
            tree[node] = tree[leftChild] * tree[rightChild];
        }
    }

    // 区间查询：查询 [l, r] 区间的乘积（闭区间）
    public long query(int l, int r) {
        if (l < 0 || r >= n || l > r) {
            throw new IllegalArgumentException("Invalid query range");
        }
        return query(0, 0, n - 1, l, r);
    }

    // 递归实现区间查询
    private long query(int node, int start, int end, int l, int r) {
        // 区间不相交，返回 1（乘法单位元）
        if (r < start || end < l) {
            return 1;
        }
        // 当前区间完全在查询区间内，返回当前节点值
        if (l <= start && end <= r) {
            return tree[node];
        }
        // 部分相交，递归查询左右子树
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        long leftProduct = query(leftChild, start, mid, l, r);
        long rightProduct = query(rightChild, mid + 1, end, l, r);
        // 返回左右子树乘积
        return leftProduct * rightProduct;
    }

}

求积 带取模

// 线段树模版 (求积取模版)
class SegmentTree {

    // 线段树数组，存储区间乘积（取模后）
    private long[] tree;
    
    // 原始数据数组
    private long[] data;
    
    // 数据长度
    private int n;
    
    // 模数
    private final long mod;

    // 构造函数，初始化线段树并指定模数
    public SegmentTree(int[] arr, long mod) {
        this.n = arr.length;
        this.data = new long[n];
        System.arraycopy(arr, 0, this.data, 0, n);
        this.mod = mod;
        // 线段树大小通常取 4*n 确保足够
        this.tree = new long[4 * n];
        build(0, 0, n - 1);
    }

    // 构建线段树（带模运算）
    private void build(int node, int start, int end) {
        if (start == end) {
            // 叶子节点：单个元素取模后存储
            tree[node] = data[start] % mod;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            // 递归构建左右子树
            build(leftChild, start, mid);
            build(rightChild, mid + 1, end);
            // 当前节点值 = 左右子树乘积 % 模
            tree[node] = (tree[leftChild] * tree[rightChild]) % mod;
        }
    }

    // 单点更新：将 index 位置的值更新为 val（带模）
    public void update(int index, int val) {
        if (index < 0 || index >= n) {
            throw new IllegalArgumentException("Index out of bounds");
        }
        data[index] = val;
        update(0, 0, n - 1, index, val);
    }

    // 递归实现单点更新（带模）
    private void update(int node, int start, int end, int index, int val) {
        if (start == end) {
            // 目标位置：更新后取模
            tree[node] = val % mod;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;

            if (index <= mid) {
                update(leftChild, start, mid, index, val);
            } else {
                update(rightChild, mid + 1, end, index, val);
            }
            // 更新当前节点值（乘积后取模）
            tree[node] = (tree[leftChild] * tree[rightChild]) % mod;
        }
    }

    // 区间查询：查询 [l, r] 区间的乘积（带模）
    public long query(int l, int r) {
        if (l < 0 || r >= n || l > r) {
            throw new IllegalArgumentException("Invalid query range");
        }
        return query(0, 0, n - 1, l, r);
    }

    // 递归实现区间查询（带模）
    private long query(int node, int start, int end, int l, int r) {
        // 区间不相交，返回 1（乘法单位元，不影响乘积）
        if (r < start || end < l) {
            return 1;
        }
        // 当前区间完全在查询区间内，返回当前节点值（已取模）
        if (l <= start && end <= r) {
            return tree[node];
        }
        // 部分相交，递归查询左右子树
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        long leftProduct = query(leftChild, start, mid, l, r);
        long rightProduct = query(rightChild, mid + 1, end, l, r);
        // 左右子树乘积后取模
        return (leftProduct * rightProduct) % mod;
    }

}