Java竞赛编程：嵌套for循环转单for循环性能优化

Hey there! Let's break down why your current code is struggling and fix it for good.

First off, your nested loop approach is a non-starter when dealing with values up to 10^9. You can't create an array of size 1e9 (that's impossible due to memory constraints), and even if you could, iterating over every element in [l, r] for each query would lead to an absurdly slow runtime—way beyond your 2-second limit.

The Fix: Difference Array with Sparse Storage #

The solution here is to use a difference array technique, but since we're dealing with massive indices, we need a sparse implementation (like a sorted map) instead of a regular array. This lets us perform each interval update in O(log n) time, and overall process all k queries in O(k log k) time—way fast enough for your needs.

Here's how it works:

• Instead of updating every element in the interval [l-1, r-1] directly, we track only the points where the value changes.
• For each query (l, r, v):
  1. Add v to the start of the interval (index l-1).
  2. Subtract v right after the end of the interval (index r).
• Later, if you need to get the value at any index, you calculate the prefix sum of all these changes up to that index.

Optimized Code (Single Loop) #

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        TreeMap<Long, Long> diffMap = new TreeMap<>();
        
        // Single loop to process all k queries
        for (int i = 0; i < k; i++) {
            long l = sc.nextLong();
            long r = sc.nextLong();
            long v = sc.nextLong();
            
            // Apply the difference array updates
            diffMap.put(l - 1, diffMap.getOrDefault(l - 1, 0L) + v);
            diffMap.put(r, diffMap.getOrDefault(r, 0L) - v);
        }
        
        // Example: If you need to query the value at a specific index x
        // long x = sc.nextLong();
        // long currentValue = 0;
        // for (long key : diffMap.headMap(x + 1).keySet()) {
        //     currentValue += diffMap.get(key);
        // }
        // System.out.println(currentValue);
    }
}

Why This Works #

• Time Efficiency: Each put operation on a TreeMap takes O(log m) time, where m is the number of unique indices we're tracking. With k queries, this totals O(k log k) time—easily under 2 seconds even for large k.
• Memory Efficiency: We only store indices where the value changes, so we don't waste space on the millions (or billions) of unused indices.

This approach completely eliminates the nested loop and handles the 10^9 scale without breaking a sweat.

内容的提问来源于stack exchange，提问作者Karan Matalia