import java.util.*;
 
class Main {
 
    // Function to create the prefix sum array
    static int[] prefixSum(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
 
        // Build the prefix array
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
 
        return prefix;
    }
 
    // Function to find the sum from index l to r
    static int optimizedSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l];
    }
 
    public static void main(String[] args) {
 
        // Original array
        int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
 
        // Create the prefix sum array
        int[] prefix = prefixSum(nums);
 
        // Range to find the sum
        int l = 3;
        int r = 7;
 
        // Print the sum
        System.out.println("Sum from index " + l + " to " + r + " = " + optimizedSum(prefix, l, r));
    }
}

aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgTWFpbiB7CgogICAgLy8gRnVuY3Rpb24gdG8gY3JlYXRlIHRoZSBwcmVmaXggc3VtIGFycmF5CiAgICBzdGF0aWMgaW50W10gcHJlZml4U3VtKGludFtdIG51bXMpIHsKICAgICAgICBpbnQgbiA9IG51bXMubGVuZ3RoOwogICAgICAgIGludFtdIHByZWZpeCA9IG5ldyBpbnRbbiArIDFdOwoKICAgICAgICAvLyBCdWlsZCB0aGUgcHJlZml4IGFycmF5CiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CiAgICAgICAgICAgIHByZWZpeFtpXSA9IHByZWZpeFtpIC0gMV0gKyBudW1zW2kgLSAxXTsKICAgICAgICB9CgogICAgICAgIHJldHVybiBwcmVmaXg7CiAgICB9CgogICAgLy8gRnVuY3Rpb24gdG8gZmluZCB0aGUgc3VtIGZyb20gaW5kZXggbCB0byByCiAgICBzdGF0aWMgaW50IG9wdGltaXplZFN1bShpbnRbXSBwcmVmaXgsIGludCBsLCBpbnQgcikgewogICAgICAgIHJldHVybiBwcmVmaXhbciArIDFdIC0gcHJlZml4W2xdOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKCiAgICAgICAgLy8gT3JpZ2luYWwgYXJyYXkKICAgICAgICBpbnRbXSBudW1zID0gezAsIDEsIDIsIDMsIDQsIDUsIDYsIDcsIDgsIDl9OwoKICAgICAgICAvLyBDcmVhdGUgdGhlIHByZWZpeCBzdW0gYXJyYXkKICAgICAgICBpbnRbXSBwcmVmaXggPSBwcmVmaXhTdW0obnVtcyk7CgogICAgICAgIC8vIFJhbmdlIHRvIGZpbmQgdGhlIHN1bQogICAgICAgIGludCBsID0gMzsKICAgICAgICBpbnQgciA9IDc7CgogICAgICAgIC8vIFByaW50IHRoZSBzdW0KICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIlN1bSBmcm9tIGluZGV4ICIgKyBsICsgIiB0byAiICsgciArICIgPSAiICsgb3B0aW1pemVkU3VtKHByZWZpeCwgbCwgcikpOwogICAgfQp9