差分数组-实现区间强度算法

package org.example;

import java.util.Map;
import java.util.TreeMap;

public class IntensitySegments {
    // 使用 TreeMap 来存储每个区间的起始位置和对应的强度
    private TreeMap<Integer, Integer> segments;

    public IntensitySegments() {
        segments = new TreeMap<>();
    }

    /**
     * 将指定区间 [from, to] 的强度增加 amount。
     *
     * @param from 起始点
     * @param to 结束点
     * @param amount 要增加的强度
     */
    public void add(int from, int to, int amount) {
        // 增加区间起始位置的强度
        segments.put(from, segments.getOrDefault(from, 0) + amount);
        // 减少区间结束位置的强度
        segments.put(to, segments.getOrDefault(to, 0) - amount);
    }

    /**
     * 将指定区间 [from, to] 的强度设置为 amount。
     *
     * @param from 起始点
     * @param to 结束点
     * @param amount 要设置的强度
     */
    public void set(int from, int to, int amount) {
        // 删除该范围内的旧的强度
        segments.entrySet().removeIf(entry -> entry.getKey() >= from && entry.getKey() <= to);

        // 将区间设置为新的强度
        segments.put(from, amount);
        segments.put(to, 0);  // 设置结束点为 0，确保在该点后不再有强度
    }

    /**
     * 将区间的强度信息转换为字符串表示。
     *
     * @return 字符串表示
     */
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("[");
        int currentIntensity = 0;

        // 遍历 TreeMap，计算每个区间的强度
        for (Map.Entry<Integer, Integer> entry : segments.entrySet()) {
            currentIntensity += entry.getValue();
            result.append("[").append(entry.getKey()).append(",").append(currentIntensity).append("],");
        }

        // 去掉最后一个逗号，并加上 "]"
        if (result.length() > 1) {
            result.setLength(result.length() - 1);
        }
        result.append("]");

        return result.toString();
    }

    // 测试用例
    public static void main(String[] args) {
        IntensitySegments segments = new IntensitySegments();

        System.out.println(segments.toString()); // 输出: []
        segments.add(10, 30, 1);
        System.out.println(segments.toString()); // 输出: [[10,1],[30,0]]
        segments.add(20, 40, 1);
        System.out.println(segments.toString()); // 输出: [[10,1],[20,2],[30,1],[40,0]]
        segments.add(10, 40, -2);
        System.out.println(segments.toString()); // 输出: [[10,-1],[20,0],[30,-1],[40,0]]


        IntensitySegments segments2 = new IntensitySegments();
        System.out.println(segments2.toString()); // 输出: []
        segments2.add(10, 30, 1);
        System.out.println(segments2.toString()); // 输出: [[10,1],[30,0]]
        segments2.add(20, 40, 1);
        System.out.println(segments2.toString()); // 输出: [[10,1],[20,2],[30,1],[40,0]]
        segments2.add(10, 40, -1);
        System.out.println(segments2.toString()); // 输出: [[10,0],[20,1],[30,0],[40,0]]
        segments2.add(10, 40, -1);
        System.out.println(segments2.toString()); // 输出: [[10,-1],[20,0],[30,-1],[40,0]]
    }
}

### 差分数组（Difference Array）概念

差分数组是一种常用于高效处理区间更新和查询的技巧。它通过记录**区间增量**而不是直接存储区间内的值，来优化更新操作。差分数组的核心思想是：对于一个区间 `[L, R]`，我们只记录区间的**开始增量**和**结束增量**，而不直接对区间内每个元素进行逐一更新。这使得区间更新变得非常高效。

### 差分数组的工作原理：

假设我们有一个长度为 `n` 的数组 `arr[]`，我们要对区间 `[L, R]` 中的所有元素加上一个值 `x`。如果直接修改区间内的每个元素，会有较高的时间复杂度（`O(R-L+1)`）。但是，如果使用差分数组，我们可以通过**记录增量**来高效处理这个问题，具体步骤如下：

1. **创建一个差分数组 `diff[]`**，其大小与原数组相同（或比原数组多 1）。
   
2. 对于区间 `[L, R]`：
   - 在 `diff[L]` 位置增加 `x`，表示从 `L` 位置开始，数组值增加 `x`。
   - 在 `diff[R + 1]` 位置减少 `x`，表示从 `R + 1` 位置开始，数组值停止增加 `x`。

3. **构造原数组**：通过差分数组 `diff[]`，我们可以通过累加得到原数组的最终值。

### 举例说明：

假设我们有一个数组 `arr[]`，并且我们要对区间 `[L, R]` 的每个元素加 `x`。

#### 初始情况：

```
arr[] = [0, 0, 0, 0, 0]   (长度为5的数组，初始值为0)
```

#### 假设要对区间 `[1, 3]` 进行加 5 操作：

1. 创建差分数组 `diff[]`（大小为 6，原数组大小 + 1）：

```
diff[] = [0, 0, 0, 0, 0, 0]  (初始化为0)
```

2. 对区间 `[1, 3]` 执行加 5 操作：

- 在 `diff[1]` 增加 5，表示从位置 1 开始，增加 5。
- 在 `diff[4]` 减少 5，表示从位置 4 开始，停止增加 5。

更新后的差分数组：

```
diff[] = [0, 5, 0, 0, -5, 0]
```

3. 最后，我们通过差分数组恢复原数组。我们需要从 `diff[]` 数组中累加得到原数组 `arr[]`：

- `arr[0] = diff[0] = 0`
- `arr[1] = arr[0] + diff[1] = 0 + 5 = 5`
- `arr[2] = arr[1] + diff[2] = 5 + 0 = 5`
- `arr[3] = arr[2] + diff[3] = 5 + 0 = 5`
- `arr[4] = arr[3] + diff[4] = 5 + (-5) = 0`

最终的原数组是：

```
arr[] = [0, 5, 5, 5, 0]
```

### 为什么差分数组可以高效处理区间更新？

- **空间复杂度**：差分数组只需要一个额外的数组，它的空间复杂度是 `O(n)`，与原数组大小相同。
- **时间复杂度**：每次对一个区间 `[L, R]` 的操作，只需要 `O(1)` 的时间。更新操作是常数时间复杂度，因此可以高效处理多个区间更新。
  
  - 在原数组上进行更新时，我们需要遍历整个区间，这样的操作是 `O(R - L + 1)`。
  - 使用差分数组时，每次只需要两次操作：`diff[L] += x` 和 `diff[R + 1] -= x`，这两步操作的时间复杂度是 `O(1)`。

### 扩展：多个区间的处理

当你需要执行多个区间的操作时，差分数组的优势更加明显。你可以为每个区间执行差分操作，而不用担心每次操作都要遍历区间内的每个元素。

### 差分数组的逆操作：构建原数组

通过差分数组得到原数组的过程叫做**前缀和**（prefix sum）：

```python
def build_array_from_diff(diff):
    arr = [0] * len(diff)
    arr[0] = diff[0]
    for i in range(1, len(diff)):
        arr[i] = arr[i-1] + diff[i]
    return arr
```

### 在 `add(from, to, amount)` 方法中的应用

在 `add(from, to, amount)` 操作中，我们实际上是在使用类似差分数组的思想：

- **`segments.put(from, segments.getOrDefault(from, 0) + amount)`**：在 `from` 点加上 `amount`，表示从 `from` 开始，强度增加 `amount`。
- **`segments.put(to, segments.getOrDefault(to, 0) - amount)`**：在 `to` 点减去 `amount`，表示从 `to` 开始，强度停止增加 `amount`。

这与差分数组的思想类似：我们没有直接去更新区间 `[from, to]` 内的每个位置，而是通过在 `from` 位置加上增量，在 `to` 位置减去增量来间接实现对区间的更新。

### 总结

差分数组是一种高效的区间更新技巧，通过记录区间的增量，避免了逐个元素的操作，极大提高了区间更新的效率。在 `add(from, to, amount)` 的实现中，我们使用了类似差分数组的技巧：在区间起始点加上增量，在结束点的下一个位置减去增量，从而控制增量的作用范围。