题目

三元组个数

解题思路

1. 朴素算法与瓶颈

最直接的方法是使用三层循环枚举 (i, j, k)，逐一判断是否满足 a_i < a_j < a_k。

复杂度分析：时间复杂度为 O(n^3)。
局限性：当 n = 2 \times 10^5 时，计算量高达 10^{15} 级，必然超时。我们需要将复杂度降低到 O(n \log n) 级别。

2. 优化策略：枚举中间项

与其漫无目的地同时寻找三个数，不如固定中间项 j。

对于任意一个位置 j（作为三元组的中间元素），如果我们能快速算出：

左边有多少个元素比 a_j 小（记为 L_j）；
右边有多少个元素比 a_j 大（记为 R_j）；

那么，根据乘法原理，以 j 为中心的三元组个数就是 L_j \times R_j。最终答案即为所有位置贡献之和：\sum (L_j \times R_j)。

这就将问题转化为：如何快速统计序列中“在某个位置左边/右边且比它小/大的数”的个数？

3. 关键技巧：离散化 (Discretization)

在统计之前，我们面临一个技术障碍：题目中 a_i 的范围高达 10^9。

若要使用树状数组或权值线段树来进行统计，通常需要以数值作为下标。显然，我们无法开辟大小为 10^9 的数组。

为什么要离散化？

我们只关心数字之间的相对大小关系（Rank），而不关心具体数值。

离散化就是将稀疏的大数值映射为紧凑的小整数（排名），从而压缩空间。

离散化步骤演示：

复制与去重：将原数组复制一份，排序并去除重复元素。
- 原数组：[100, 500000000, 100, 200]
- 去重排序后：[100, 200, 500000000]
建立映射：确定每个数值在去重数组中的下标（排名）。
- 100 \to 排名 1
- 200 \to 排名 2
- 500000000 \to 排名 3
替换：将原数组中的大整数替换为对应的排名。
- 离散化后数组：[1, 3, 1, 2]

经过离散化，数组值的范围被压缩到了 [1, n]，完全满足树状数组的空间要求。

4. 高效统计：树状数组 (Fenwick Tree)

我们使用树状数组来维护数值出现的频率。树状数组支持单点修改和前缀和查询，时间复杂度均为 O(\log n)。

**注意：这里维护的是频率而非原数组！**想象一个辅助数组 freq[1..M]：

freq[x] 表示：当前已经处理过的元素中，值等于 x 的有多少个？
初始时所有 freq[x] = 0
每当我们“看到”一个离散化后的值 v，就执行：freq[v] += 1

那么：

“小于等于 v 的元素个数” = freq[1] + freq[2] + ... + freq[v] → 这就是 前缀和！
“小于 v 的元素个数” = 前缀和到 v-1
“大于 v 的元素个数” = 总数 - 前缀和到 v

👉 所以，树状数组在这里 维护的是 freq 数组的前缀和结构，而不是原数组 b 本身！

具体实现流程：

第一步：计算 L_j（左边比它小的个数）

我们从左向右遍历数组，对于每个元素 x（这里的 x 是离散化后的排名）：

查询 (Query)：调用 query(x - 1)。
- 这表示统计目前为止，树状数组中值在 [1, x-1] 范围内的元素总数，即左边比当前数小的个数。
更新 (Update)：调用 update(x, 1)。
- 将当前数值 x 加入树状数组（对应位置计数 +1），供后续元素查询。

第二步：计算 R_j（右边比它大的个数）

为了方便，我们可以清空树状数组，然后从右向左遍历数组：

查询 (Query)：
- 右边比它大的个数 = 当前右边已遍历的总数 - query(x)（小于等于它的个数）。
更新 (Update)：调用 update(x, 1)，将当前数加入统计。

第三步：统计答案

遍历每个位置 i，累加 L_i \times R_i，并注意对 998244353 取模。

复杂度总结

时间复杂度：离散化排序 O(n \log n)，两次遍历配合树状数组操作也是 O(n \log n)。总复杂度 O(n \log n)，可以通过 2 \times 10^5 的数据。
空间复杂度：需要 O(n) 的空间存储辅助数组和树状数组。

参考代码

方法一：暴力枚举（无法AC）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long MOD = 998244353;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        long count = 0;
        // 三重循环枚举所有可能的三元组 (i, j, k)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // 检查是否满足 a[i] < a[j] < a[k]
                    if (a[i] < a[j] && a[j] < a[k]) {
                        count = (count + 1) % MOD;
                    }
                }
            }
        }

        System.out.println(count);
    }
}

方法二：树状数组

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long MOD = 998244353;
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 离散化：将原数组值映射到连续的小整数
        // 去重：使用TreeSet自动排序去重
        TreeSet<Integer> set = new TreeSet<>();
        for (int x : a) {
            set.add(x);
        }
        // 建立映射：值 -> 排名（从1开始）
        Map<Integer, Integer> map = new HashMap<>();
        int idx = 1;
        for (int x : set) {
            map.put(x, idx++);
        }
        // 获取离散化后的数组
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = map.get(a[i]);
        }
        int size = set.size(); // 离散化后的最大值

        // rightCount[i] 表示在位置i右边，值大于a[i]的元素个数
        long[] rightCount = new long[n];
        FenwickTree rightTree = new FenwickTree(size);

        // 从右往左遍历，计算每个位置右边大于当前值的个数
        for (int i = n - 1; i >= 0; i--) {
            // 查询比当前值大的元素个数 = 总数 - 小于等于当前值的个数
            // 树状数组维护的是已经处理过的元素（即右边的元素）
            rightCount[i] = rightTree.query(size) - rightTree.query(b[i]);
            // 将当前元素加入树状数组
            rightTree.update(b[i], 1);
        }

        // leftCount[i] 表示在位置i左边，值小于a[i]的元素个数
        long[] leftCount = new long[n];
        FenwickTree leftTree = new FenwickTree(size);

        // 从左往右遍历，计算每个位置左边小于当前值的个数
        for (int i = 0; i < n; i++) {
            // 查询比当前值小的元素个数 = 小于当前值的个数
            leftCount[i] = leftTree.query(b[i] - 1);
            // 将当前元素加入树状数组
            leftTree.update(b[i], 1);
        }

        // 计算最终答案：对每个中间位置j，贡献为 leftCount[j] * rightCount[j]
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += leftCount[i] * rightCount[i];
        }

        System.out.println(ans % MOD);
    }

    // 树状数组（Fenwick Tree）实现
    static class FenwickTree {
        private int[] tree;
        private int n;

        public FenwickTree(int size) {
            this.n = size;
            this.tree = new int[n + 1]; // 树状数组下标从1开始
        }

        // 单点更新：在位置index增加delta
        public void update(int index, int delta) {
            while (index <= n) {
                tree[index] += delta;
                index += index & (-index); // lowbit操作
            }
        }

        // 前缀查询：查询[1, index]的和
        public long query(int index) {
            if (index <= 0) return 0; // 边界处理
            long sum = 0;
            while (index > 0) {
                sum += tree[index];
                index -= index & (-index); // lowbit操作
            }
            return sum;
        }
    }
}

最长上升子序列

解题思路

1. 朴素动态规划 (DP)

最长上升子序列 (LIS) 是一个经典的动态规划问题。

我们要定义状态 dp[i] 表示：以第 i 个数字 a[i] 结尾的最长上升子序列的长度。

状态转移：

为了算出 dp[i]，我们需要回头看 i 之前的所有位置 j (0 \le j < i)。

如果 a[j] < a[i]，说明 a[i] 可以接在 a[j] 后面，形成一个更长的序列。

我们要找从哪个 j 接过来最长，即：

dp[i] = \max(\{dp[j] \mid j < i, a[j] < a[i]\}) + 1

如果找不到这样的 j，说明 a[i] 只能自己另起炉灶，长度为 1。
瓶颈分析：

这个算法有两层循环：外层遍历 i，内层遍历 j。

时间复杂度是 O(n^2)。当 n = 2 \times 10^5 时，运算量高达 4 \times 10^{10}，这对于通常限制 10^8 次运算的评测机来说，是绝对会超时 (TLE) 的。

2. 优化策略：数据结构加速

我们需要优化内层的查找过程。

回顾我们的需求：在处理 a[i] 时，我们需要找到一个值小于 a[i] 的之前的元素，且该元素的 dp 值最大。

这就把问题转化为了一个区间最大值查询 (Range Maximum Query) 问题：

查询：在数值范围 [1, a[i]-1] 内，目前已知的最大 dp 值是多少？
更新：算出当前的 dp[i] 后，将其更新到数值 a[i] 的位置上。

如果我们用树状数组来维护这个“数值到最大长度”的映射，查询和更新的时间复杂度都能降到 O(\log n)。

3. 前置处理：离散化 (Discretization)

和上一题一样，我们面临 a_i 取值范围过大 (10^9) 的问题。树状数组无法直接以 10^9 作为下标。

因为 LIS 只关心元素间的相对大小，我们可以通过离散化将数值映射为排名。

离散化演示：

原数组：[10, 1000, 20, 10]
去重排序：[10, 20, 1000]
映射关系：10 \to 1, 20 \to 2, 1000 \to 3
转换后：[1, 3, 2, 1]

4. 树状数组 (Fenwick Tree) 实现逻辑

关键点：这里树状数组维护的不是前缀和，而是“前缀最大值”！

为了理解为什么用树状数组，请先想象一个辅助数组 max_len[1..N]（其中下标代表离散化后的数值）：

max_len[v] 的含义：在目前已经处理过的数字中，以“数值 v”结尾的最长上升子序列长度是多少？
初始时，所有 max_len 均为 0。

当我们遍历到原数组的一个新数值 v 时，我们的目标是：

找前驱：我要接在一个比我小（数值 < v）的数字后面。为了让总长度最长，我需要知道在数值范围 [1, v-1] 内，谁的 max_len 最大？

👉 这就是在求 max_len 数组的前缀最大值 (Prefix Max)！
接上去：算出当前长度 curr = query(v-1) + 1。
更新我：现在我也能作为结尾了，长度是 curr。我们需要更新 max_len[v]。

👉 这就是单点更新 (Point Update)。

树状数组的角色：

普通树状数组用 + 维护前缀和，而在这里，我们将操作换成 Math.max，用它来维护 max_len 数组的结构。

query(v-1)：快速返回 \max(max\_len[1], max\_len[2], \dots, max\_len[v-1])。
update(v, curr)：将 max_len[v] 更新为 curr（同时维护树状结构中的父节点最大值）。

算法流程演示：

假设输入数组为 1 3 4 2，离散化后排名亦为 1 3 4 2。

步骤	当前数值 (Rank)	动作 1：找更小的最大值 (Query)	动作 2：计算与更新 (Update)	辅助数组 max_len 及其含义
i=0	1	查 `[1, 0]` (无) \to 0	长度0+1=\mathbf{1} 更新位置 1	`max_len[1]=1` (以1结尾最长为1)
i=1	3	查 `[1, 2]` (只有Rank 1) \to 1	长度1+1=\mathbf{2} 更新位置 3	`max_len[3]=2` (以3结尾最长为2)
i=2	4	查 `[1, 3]` (Rank 1,3中最大是2) \to 2	长度2+1=\mathbf{3} 更新位置 4	`max_len[4]=3` (以4结尾最长为3)
i=3	2	查 `[1, 1]` (Rank 1) \to 1	长度1+1=\mathbf{2} 更新位置 2	`max_len[2]=2` (以2结尾最长为2)

最终答案是所有步骤中计算出的长度的最大值，即 3。

复杂度总结

时间复杂度：
- 离散化：O(n \log n)。
- DP 过程：遍历 n 次，每次进行树状数组操作 O(\log n)，共 O(n \log n)。
- 总计：O(n \log n)，完美解决 2 \times 10^5 的数据规模。
空间复杂度：
- 需要 O(n) 的空间存储离散化数组和树状数组。

参考代码

方法一：动态规划（无法AC）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
    
        // dp[i] 表示以第 i 个元素结尾的最长上升子序列长度
        int[] dp = new int[n];
        int maxLen = 0;
    
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 每个元素至少自己构成一个长度为1的子序列
            for (int j = 0; j < i; j++) {
                // 如果 a[j] < a[i]，则可以将 a[i] 接在 a[j] 后面
                if (a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    
        System.out.println(maxLen);
    }
}

方法二：树状数组

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 离散化：将原数组值映射到连续的小整数
        TreeSet<Integer> set = new TreeSet<>();
        for (int x : a) {
            set.add(x);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int idx = 1;
        for (int x : set) {
            map.put(x, idx++);
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = map.get(a[i]);
        }
        int size = set.size(); // 离散化后的最大值

        // 树状数组：维护以每个值结尾的最长上升子序列长度
        FenwickTree tree = new FenwickTree(size);

        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            // 查询比当前值小的所有值对应的最大长度
            int prevMax = tree.query(b[i] - 1);
            int currentLen = prevMax + 1;
            maxLen = Math.max(maxLen, currentLen);
            // 更新树状数组：在位置b[i]处，将当前长度与已存储长度取最大值
            tree.update(b[i], currentLen);
        }

        System.out.println(maxLen);
    }

    // 树状数组实现（维护前缀最大值）
    static class FenwickTree {
        private int[] tree;
        private int n;

        public FenwickTree(int size) {
            this.n = size;
            this.tree = new int[n + 1]; // 1-indexed
        }

        // 更新：在位置index处，将值更新为max(当前值, value)
        public void update(int index, int value) {
            while (index <= n) {
                if (value > tree[index]) {
                    tree[index] = value;
                }
                index += index & (-index);
            }
        }

        // 查询：查询[1, index]的最大值
        public int query(int index) {
            if (index <= 0) return 0;
            int maxVal = 0;
            while (index > 0) {
                if (tree[index] > maxVal) {
                    maxVal = tree[index];
                }
                index -= index & (-index);
            }
            return maxVal;
        }
    }
}

区间开根号

解题思路

1. 问题分析与瓶颈

我们需要支持两种操作：

区间修改：将 [l, r] 内的每个数 a_i 变为 \lfloor \sqrt{a_i} \rfloor。
区间查询：求 [l, r] 的和。

如果使用朴素暴力法，每次修改遍历区间，时间复杂度为 O(N \times M)。在 N, M \le 10^5 的规模下，计算量高达 10^{10}，必然超时 (TLE)。因此，我们需要借助于线段树。

2. 难点：懒标记失效

在常规的线段树区间修改（如区间加法、区间赋值）中，我们通常使用懒标记 (Lazy Propagation) 来避免频繁下探到叶子节点。

然而，开根号操作不具备“可叠加性”。

区间加法：+2 再 +3 等于 +5。
区间开根：\sqrt{\sqrt{x}} 无法简单合并为一个简单的线性标记；且 \sqrt{a+b} \neq \sqrt{a} + \sqrt{b}，我们也无法直接通过当前区间的和来推算开根后的和。

这意味着，看似我们必须深入到每个叶子节点去修改每一个值，这退化回了暴力法。怎么办？

3. 突破口：数值收敛速度

让我们观察一下对一个大整数不断开根号会发生什么。

假设有一个极大的数 x = 10^{18}（Long型的上限）：

\sqrt{10^{18}} = 10^9
\sqrt{10^9} \approx 31622
\sqrt{31622} \approx 177
\sqrt{177} \approx 13
\sqrt{13} \approx 3
\sqrt{3} = 1
\sqrt{1} = 1 ...（之后永远保持为 1）

关键性质：任意 64 位整数，经过仅仅 6 到 7 次开根号操作后，就会变成 1（如果是 0 则保持 0）。

一旦一个数变为 0 或 1，无论再进行多少次开根号操作，它的值都不会改变。

4. 优化策略：剪枝 (Pruning)

基于上述性质，我们可以采用一种**“势能线段树”**（或称暴力剪枝线段树）的策略：

维护区间最大值：在线段树的每个节点中，除了维护 sum（区间和），额外维护一个 max（区间内元素的最大值）。
暴力递归与剪枝：
- 当执行区间修改时，我们尝试向子节点递归。
- 剪枝条件：如果在递归过程中，发现当前节点的 max <= 1，说明该区间内所有数都是 0 或 1。此时开根号没有任何意义，直接 return，不再向下递归。
- 单点更新：如果 max > 1，则继续递归，直到叶子节点进行开根号运算，并在回溯时更新父节点的 sum 和 max。

5. 复杂度分析

虽然看起来我们在做单点更新，但实际上每个数最多只会被有效修改约 6 次。

对于整个数组，总的有效修改次数上限约为 6 \times N。
每次修改在线段树上的代价是 O(\log N)。
总的时间复杂度约为 O((N + M) \log N \times K)，其中 K \approx 6。

这完全足以通过本题的时间限制。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 数组长度
        int m = sc.nextInt();  // 操作次数
    
        // 初始化数组（下标0~n-1对应题目1~n）
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
    
        // 构建线段树（数组大小为4*n）
        SegmentTree segTree = new SegmentTree(arr);
    
        // 处理m次操作
        for (int i = 0; i < m; i++) {
            int op = sc.nextInt();  // 操作类型
            int l = sc.nextInt() - 1;  // 转换为0-based下标
            int r = sc.nextInt() - 1;
        
            if (op == 1) {
                // 操作1：区间开方
                segTree.update(l, r);
            } else {
                // 操作2：区间求和
                System.out.println(segTree.query(l, r));
            }
        }
    }
}

class SegmentTree {
    private long[] treeSum;   // 线段树：存储区间和
    private int[] treeMax;    // 线段树：存储区间最大值
    private int n;            // 原数组长度
  
    // 构造函数：初始化线段树
    public SegmentTree(int[] arr) {
        n = arr.length;
        // 线段树大小为4倍原数组长度
        treeSum = new long[4 * n];
        treeMax = new int[4 * n];
    
        // 构建线段树（索引从0开始）
        build(0, 0, n - 1, arr);
    }
  
    // 构建线段树（递归）
    private void build(int node, int left, int right, int[] arr) {
        if (left == right) {
            // 叶子节点：初始化值
            treeSum[node] = arr[left];
            treeMax[node] = arr[left];
            return;
        }
    
        int mid = (left + right) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
    
        // 递归构建左右子树
        build(leftChild, left, mid, arr);
        build(rightChild, mid + 1, right, arr);
    
        // 合并子树信息
        treeSum[node] = treeSum[leftChild] + treeSum[rightChild];
        treeMax[node] = Math.max(treeMax[leftChild], treeMax[rightChild]);
    }
  
    // 区间开方操作（更新）
    public void update(int l, int r) {
        update(0, 0, n - 1, l, r);
    }
  
    // 递归更新区间
    private void update(int node, int left, int right, int l, int r) {
        // 情况1：当前区间与查询区间无交集
        if (r < left || l > right) {
            return;
        }
    
        // 情况2：当前区间完全包含在查询区间内
        if (l <= left && right <= r) {
            // 优化点：如果最大值≤1，说明无需更新
            if (treeMax[node] <= 1) {
                return;
            }
        
            // 情况2.1：叶子节点（直接开方）
            if (left == right) {
                treeSum[node] = (long) Math.sqrt(treeSum[node]);
                treeMax[node] = (int) treeSum[node];
                return;
            }
        }
    
        // 递归更新左右子树
        int mid = (left + right) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
    
        update(leftChild, left, mid, l, r);
        update(rightChild, mid + 1, right, l, r);
    
        // 合并子树信息
        treeSum[node] = treeSum[leftChild] + treeSum[rightChild];
        treeMax[node] = Math.max(treeMax[leftChild], treeMax[rightChild]);
    }
  
    // 区间求和查询
    public long query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
  
    // 递归查询区间和
    private long query(int node, int left, int right, int l, int r) {
        // 情况1：无交集
        if (r < left || l > right) {
            return 0;
        }
    
        // 情况2：完全包含
        if (l <= left && right <= r) {
            return treeSum[node];
        }
    
        // 递归查询左右子树
        int mid = (left + right) / 2;
        long leftSum = query(2 * node + 1, left, mid, l, r);
        long rightSum = query(2 * node + 2, mid + 1, right, l, r);
    
        return leftSum + rightSum;
    }
}

区间最大字段和

解题思路（线段树）

1. 为什么不能直接分治？

这是一个经典的 GSS (Maximum Contiguous Subsequence Sum) 问题。

最直观的想法是使用线段树，每个节点维护当前区间的“最大子段和” (maxSum)。

但在合并两个子节点（左儿子 L 和右儿子 R）时，我们遇到了问题：

父节点的 maxSum 不一定只是 max(L.maxSum, R.maxSum)。

最优秀的子段完全有可能跨越中点，一部分在左边，一部分在右边。

为了处理这种“跨越边界”的情况，我们需要维护更多的信息。

2. 核心策略：维护四个变量

为了能够正确地合并两个区间，线段树的每个节点需要记录以下 4 个值：

total (区间总和)：
- 用于计算跨越区间的和。
prefix (最大前缀和)：
- 从区间最左端开始，向右延伸所能达到的最大和。
suffix (最大后缀和)：
- 从区间最右端开始，向左延伸所能达到的最大和。
maxSum (最大子段和)：
- 当前区间内任意连续子段的最大和（即最终答案）。

3. 合并逻辑 (PushUp / Merge)

当我们要把左节点 L 和右节点 R 合并成父节点 P 时，逻辑如下：

更新 total：
- 很简单，直接相加：P.total = L.total + R.total
更新 prefix (最大前缀)：
- 父节点的最大前缀有两种可能：
  1. 由左儿子的最大前缀组成（没跨过中点）。
  2. 由左儿子的整个区间 + 右儿子的最大前缀组成（跨过了中点）。
- 公式：P.prefix = max(L.prefix, L.total + R.prefix)
更新 suffix (最大后缀)：
- 同理，从右往左看：
- 公式：P.suffix = max(R.suffix, R.total + L.suffix)
更新 maxSum (最大子段和)：
- 最强子段有三种来源：
  1. 完全在左儿子里 (L.maxSum)。
  2. 完全在右儿子里 (R.maxSum)。
  3. 跨越中点：左儿子的最大后缀 + 右儿子的最大前缀 (L.suffix + R.prefix)。
- 公式：P.maxSum = max(L.maxSum, R.maxSum, L.suffix + R.prefix)

4. 数值演示

为了直观理解“跨越合并”的过程，我们来看一个具体的例子。

假设父节点需要合并两个子区间：

左区间 (Left)：[-4, 3, 4] （总和为 3）
右区间 (Right)：[5, 2, -6] （总和为 1）

显然，整个合并后的区间是 [-4, 3, 4, 5, 2, -6]，肉眼可见最大子段和应该是中间那一坨 3, 4, 5, 2，总和为 14。

我们来看看程序是如何通过维护的 4 个变量算出这个 14 的：

属性	左节点 L [-4, 3, 4]	右节点 R [5, 2, -6]	父节点 P (合并结果)	计算逻辑详解
Total (区间总和)	3	1	4	直接相加：L.total + R.total = 3 + 1 = 4
Prefix (最大前缀)	3 (来源: -4+3+4)	7 (来源: 5+2)	10	比较： 1. 左前缀 (3) 2. 左总和 + 右前缀 (3 + 7 = 10) 👉 取最大值 10
Suffix (最大后缀)	7 (来源: 3+4)	1 (来源: 5+2-6)	8	比较： 1. 右后缀 (1) 2. 右总和 + 左后缀 (1 + 7 = 8) 👉 取最大值 8
MaxSum (最大子段)	7 (来源: 3+4)	7 (来源: 5+2)	14	三者取最大： 1. 左最大子段 (7) 2. 右最大子段 (7) 3.跨越中点 (L.suffix + R.prefix = 7 + 7 = 14) 👉 最终答案 14

结论：

通过观察 MaxSum 的计算过程，我们可以发现：虽然左边和右边各自内部的最大子段和都只有 7，但因为它们在“接口”处分别贡献了强有力的后缀 7 和前缀 7，两者结合（7+7=14）成为了新的最大值。这就是维护 prefix 和 suffix 的意义所在。

5. 复杂度分析

时间复杂度：
- 构建线段树：O(N)。
- 单点修改：O(\log N)。
- 区间查询：O(\log N)。
- 对于 2 \times 10^5 的数据，完全可以 AC。
空间复杂度：
- 线段树需要开 4N 的数组空间，复杂度为 O(N)。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 数组长度
        int q = sc.nextInt();  // 操作次数

        // 初始化数组（下标0~n-1对应题目1~n）
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 构建线段树
        SegmentTree segTree = new SegmentTree(arr);

        // 处理q次操作
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();  // 操作类型

            if (op == 1) {
                // 修改操作：将位置x（1-based）修改为d
                int pos = sc.nextInt() - 1;  // 转换为0-based位置
                int val = sc.nextInt();      // 值（不要减1！）
                segTree.update(pos, val);
            } else {
                // 查询操作：查询区间[l, r]（1-based）的最大子段和
                int l = sc.nextInt() - 1;  // 转换为0-based左边界
                int r = sc.nextInt() - 1;  // 转换为0-based右边界
                System.out.println(segTree.query(l, r));
            }
        }
    }
}

class SegmentTree {
    // 线段树节点存储结构
    private static class Node {
        long total;   // 区间总和
        long prefix;  // 区间最大前缀和
        long suffix;  // 区间最大后缀和
        long maxSum;  // 区间最大子段和

        // 构造函数：初始化节点（叶子节点）
        public Node(long value) {
            this.total = value;
            this.prefix = value;
            this.suffix = value;
            this.maxSum = value;
        }
    }

    private Node[] tree;  // 线段树数组
    private int n;        // 原数组长度

    // 构造函数：初始化线段树
    public SegmentTree(int[] arr) {
        n = arr.length;
        // 线段树大小为4倍原数组长度
        tree = new Node[4 * n];
        build(0, 0, n - 1, arr);
    }

    // 构建线段树（递归）
    private void build(int node, int left, int right, int[] arr) {
        if (left == right) {
            // 叶子节点：初始化为单个元素
            tree[node] = new Node(arr[left]);
            return;
        }

        int mid = (left + right) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;

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

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

    // 合并两个子区间的信息
    private Node merge(Node left, Node right) {
        Node node = new Node(0);
        node.total = left.total + right.total;

        // 最大前缀和 = max(左前缀, 左总和 + 右前缀)
        node.prefix = Math.max(left.prefix, left.total + right.prefix);

        // 最大后缀和 = max(右后缀, 右总和 + 左后缀)
        node.suffix = Math.max(right.suffix, right.total + left.suffix);

        // 最大子段和 = max(左最大, 右最大, 左后缀+右前缀)
        node.maxSum = Math.max(left.maxSum, right.maxSum);
        node.maxSum = Math.max(node.maxSum, left.suffix + right.prefix);

        return node;
    }

    // 更新操作：将位置idx的值改为val
    public void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }

    // 递归更新线段树
    private void update(int node, int left, int right, int idx, int val) {
        if (left == right) {
            // 叶子节点：直接更新
            tree[node] = new Node(val);
            return;
        }

        int mid = (left + right) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;

        if (idx <= mid) {
            update(leftChild, left, mid, idx, val); // 更新左子树
        } else {
            update(rightChild, mid + 1, right, idx, val); // 更新右子树
        }

        // 更新当前节点（合并子节点信息）
        tree[node] = merge(tree[leftChild], tree[rightChild]);
    }

    // 查询操作：查询区间[l, r]的最大子段和
    public long query(int l, int r) {
        return query(0, 0, n - 1, l, r).maxSum;
    }

    // 递归查询区间最大子段和
    private Node query(int node, int left, int right, int l, int r) {
        // 情况1：当前区间完全在查询区间外
        if (r < left || l > right) {
            return null;
        }

        // 情况2：当前区间完全在查询区间内
        if (l <= left && right <= r) {
            return tree[node];
        }

        int mid = (left + right) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;

        Node leftResult = query(leftChild, left, mid, l, r);
        Node rightResult = query(rightChild, mid + 1, right, l, r);

        // 情况3：查询区间跨越左右子树
        if (leftResult == null) {
            return rightResult;
        }
        if (rightResult == null) {
            return leftResult;
        }

        // 合并左右查询结果
        return merge(leftResult, rightResult);
    }
}

罗文彬

蓝桥杯第19次带练

题目

三元组个数

解题思路

1. 朴素算法与瓶颈

2. 优化策略：枚举中间项

3. 关键技巧：离散化 (Discretization)

4. 高效统计：树状数组 (Fenwick Tree)

复杂度总结

参考代码

方法一：暴力枚举（无法AC）

方法二：树状数组

最长上升子序列

解题思路

1. 朴素动态规划 (DP)

2. 优化策略：数据结构加速

3. 前置处理：离散化 (Discretization)

4. 树状数组 (Fenwick Tree) 实现逻辑

复杂度总结

参考代码

方法一：动态规划（无法AC）

方法二：树状数组

区间开根号

解题思路

1. 问题分析与瓶颈

2. 难点：懒标记失效

3. 突破口：数值收敛速度

4. 优化策略：剪枝 (Pruning)

5. 复杂度分析

参考代码

区间最大字段和

解题思路（线段树）

1. 为什么不能直接分治？

2. 核心策略：维护四个变量

3. 合并逻辑 (PushUp / Merge)

4. 数值演示

5. 复杂度分析

参考代码

罗文彬

题目

三元组个数

解题思路

1. 朴素算法与瓶颈

2. 优化策略：枚举中间项

3. 关键技巧：离散化 (Discretization)

4. 高效统计：树状数组 (Fenwick Tree)

复杂度总结

参考代码

方法一：暴力枚举（无法AC）

方法二：树状数组

最长上升子序列

解题思路

1. 朴素动态规划 (DP)

2. 优化策略：数据结构加速

3. 前置处理：离散化 (Discretization)

4. 树状数组 (Fenwick Tree) 实现逻辑

复杂度总结

参考代码

方法一：动态规划（无法AC）

方法二：树状数组

区间开根号

解题思路

1. 问题分析与瓶颈

2. 难点：懒标记失效

3. 突破口：数值收敛速度

4. 优化策略：剪枝 (Pruning)

5. 复杂度分析

参考代码

区间最大字段和

解题思路（线段树）

1. 为什么不能直接分治？

2. 核心策略：维护四个变量

3. 合并逻辑 (PushUp / Merge)

4. 数值演示

5. 复杂度分析

参考代码

蓝桥杯第18次带练

蓝桥杯第20次带练

罗文彬