线段树实现计算矩形总面积的边界与性能问题排查

给定一组轴对齐矩形，每个矩形rectangle[i] = [x1, y1, x2, y2]，其中(x1, y1)是左下角坐标，(x2, y2)是右上角坐标。需计算所有矩形在平面上的总面积，结果对10^9 + 7取模。
注意：y1恒为0。

1. 第一行输入整数N，表示矩形数量。
2. 接下来N行每行输入四个整数：x1, y1, x2, y2。

输出总面积对10^9 + 7取模的结果。

• 1 <= N <= 40000
• rectanges[i].length = 4
• 0 <= rectangles[i][j] <= 10^9
• 总面积不会超过2^63 - 1，可存入64位有符号整数

3
0 0 2 2
1 0 2 3
1 0 3 1

6

解释1 #

总面积为6。

我使用**带懒标记的线段树（segment tree with lazy propagation）**实现了解法，以下是包含调试日志的代码：

代码 #

import java.util.*;

public class RectangleArea {

    private static final int MOD = 1_000_000_007;

    public long findArea(int n, int[][] rectangles) {
        // Step 1: Coordinate compression for x-coordinates
        TreeSet<Integer> xCoords = new TreeSet<>();
        for (int[] rect : rectangles) {
            xCoords.add(rect[0]);
            xCoords.add(rect[2]);
        }

        // Create mapping for x-coordinates
        List<Integer> xList = new ArrayList<>(xCoords);
        Map<Integer, Integer> xMap = new HashMap<>();
        for (int i = 0; i < xList.size(); i++) {
            xMap.put(xList.get(i), i);
        }

        // Debugging: Log compressed coordinates mapping
        System.out.println("Compressed X Coordinates Mapping: " + xMap);

        // Step 2: Build events for rectangles
        int[][] events = new int[2 * n][4];
        int index = 0;
        for (int[] rect : rectangles) {
            int x1 = xMap.get(rect[0]), x2 = xMap.get(rect[2]);
            events[index++] = new int[]{rect[1], x1, x2, 1};  // Start event
            events[index++] = new int[]{rect[3], x1, x2, -1}; // End event
        }

        // Sort events by y-coordinate
        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));

        // Debugging: Log sorted events
        System.out.println("Sorted Events:");
        for (int[] event : events) {
            System.out.println(Arrays.toString(event));
        }

        // Step 3: Segment tree initialization
        int m = xList.size();
        SegmentTree segTree = new SegmentTree(m);

        // Step 4: Process events and calculate total area
        long totalArea = 0;
        int prevY = events[0][0];

        for (int[] event : events) {
            int y = event[0], x1 = event[1], x2 = event[2], type = event[3];

            // Calculate the area covered between prevY and current y
            long width = segTree.query(0, m - 1);
            totalArea = (totalArea + width * (y - prevY)) % MOD;

            // Debugging: Log current status
            System.out.println("Current Y: " + y + ", Prev Y: " + prevY + ", Width: " + width);
            System.out.println("Intermediate Total Area: " + totalArea);

            // Update the segment tree for this event
            segTree.update(x1, x2 - 1, type);

            // Debugging: Log segment tree state after update
            System.out.println("Segment Tree after update for event: " + Arrays.toString(event) + ": " + Arrays.toString(segTree.tree));

            prevY = y;
        }

        return totalArea;
    }

    static class SegmentTree {
        private int[] tree, lazy;
        private int size;

        public SegmentTree(int size) {
            this.size = size;
            this.tree = new int[4 * size];
            this.lazy = new int[4 * size];
        }

        public void update(int l, int r, int val) {
            update(0, 0, size - 1, l, r, val);
        }

        private void update(int node, int start, int end, int l, int r, int val) {
            if (lazy[node] != 0) {
                tree[node] = (lazy[node] > 0) ? (end - start + 1) : 0;
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                lazy[node] = 0;
            }

            if (start > end || start > r || end < l) return;

            if (start >= l && end <= r) {
                lazy[node] += val;
                tree[node] = (lazy[node] > 0) ? (end - start + 1) : 0;
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                return;
            }

            int mid = (start + end) / 2;
            update(2 * node + 1, start, mid, l, r, val);
            update(2 * node + 2, mid + 1, end, l, r, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }

        public long query(int l, int r) {
            return query(0, 0, size - 1, l, r);
        }

        private long query(int node, int start, int end, int l, int r) {
            if (lazy[node] != 0) {
                tree[node] = (lazy[node] > 0) ? (end - start + 1) : 0;
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                lazy[node] = 0;
            }

            if (start > end || start > r || end < l) return 0;

            if (start >= l && end <= r) return tree[node];

            int mid = (start + end) / 2;
            long left = query(2 * node + 1, start, mid, l, r);
            long right = query(2 * node + 2, mid + 1, end, l, r);
            return left + right;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] rectangles = new int[n][4];
        for (int i = 0; i < n; i++) {
            rectangles[i][0] = scanner.nextInt();
            rectangles[i][1] = scanner.nextInt();
            rectangles[i][2] = scanner.nextInt();
            rectangles[i][3] = scanner.nextInt();
        }
        scanner.close();

        long result = new RectangleArea().findArea(n, rectangles);
        System.out.println("Final Area: " + result);
    }
}

• 重叠区间未正确合并。
• 边界用例的中间区域计算因线段树更新错误而失败。
• 我的懒标记传播（lazy propagation）逻辑可能存在缺陷。
• 大测试用例下性能不佳。

1. 记录压缩后的坐标映射。
2. 记录排序后的事件。
3. 记录中间面积计算结果及线段树状态。
4. 通过手动检查树状态验证懒标记传播逻辑。

我的线段树实现存在什么问题？懒标记传播或事件处理是否存在逻辑缺陷？若有，该如何修复？或者是否有更高效的解法？

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