public static long arrayManipulation(int n, List<List<Integer>> queries) {
        long[] arr = new long[n + 1];

        for (List<Integer> query : queries) {
            int a = query.get(0);
            int b = query.get(1);
            int k = query.get(2);
            arr[a - 1] += k;
            arr[b] -= k;
        }

        long max = 0;
        long sum = 0;
        for (long num : arr) {
            sum += num;
            max = Math.max(max, sum);
        }

        return max;
    }

    public static long arrayManipulation(int n, List<List<Integer>> queries) {
    // Write your code here
        long[] tmp = new long[n];        
        long max=0,tmpSum=0;
        int a, b, k;
        for (List<Integer> query : queries) {
            a = query.get(0);
            b = query.get(1);
            k = query.get(2);

            tmp[a-1] += k;
             if (b < n) {
                tmp[b] -= k;
            }
        }
        
        for (int i = 0; i < n; i++) {
            tmpSum += tmp[i];
            max = Math.max(max, tmpSum);
        }
        return max;

    }

def arrayManipulation(n, queries):
    l = []
    for a, b, k in queries:
        l.append((a-1, k))
        l.append((b, -k))
    l.sort()
    curr_sum = 0
    best = -1
    curr_index = 0
    for idx, val in l:
        if idx != curr_index:
            best = max(best, curr_sum)
            curr_index = idx
        curr_sum += val
    return best

#define CUTOFF 5000

inline int section(const int& i,const int& sn){
    return i/sn;
}

long simulate(int n,vector<vector<int>>& queries){
    long* sum=new long[n+1];
    long res;
    for(int i=0;i<n+1;i++) sum[i]=0;
    
    int a,b,k;
    for(int i=0;i<queries.size();i++){
        a=queries[i][0];
        b=queries[i][1];
        k=queries[i][2];
        for(int i=a;i<=b;i++) sum[i]+=k;
    }
    res=*std::max_element(sum,sum+n+1);
    delete[] sum;
    return res;
}

long arrayManipulation(int n, vector<vector<int>> queries) {
//sqrt(n+1) = #sections
if(n<CUTOFF) return simulate(n,queries);
int sn=(int)std::sqrt((double)n+1);
long* sum=new long[n+1];
long* sections=new long[sn]; // [0 -- sqrt(n)) section 0, etc....
for(int i=0;i<n+1;i++) sum[i]=0;
for(int i=0;i<sn;i++) sections[i]=0;
long res;
int a,b,k;

for(int i=0;i<queries.size();i++){
    a=queries[i][0];
    b=queries[i][1];
    k=queries[i][2];
    if(b-a>2*sn){
        for(int j=a;j<sn*(section(a,sn)+1);j++) sum[j]+=k;
        for(int j=(section(a,sn)+1);(j+1)*sn<=b;j++) sections[j]+=k;
        for(int j=sn*section(b,sn);j<=b;j++) sum[j]+=k;
    }
}

for(int i=0;i<n+1;i++) sum[i]+=sections[section(i,sn)];
res=*std::max_element(sum,sum+n+1);
delete[] sum;
delete[] sections;
return res;
}