SQRT Decompostion

#include <bits/stdc++.h>
using namespace std;

const int maxN = 2 * 1e5 + 100;
const int block_size = 450;
int input[maxN];
int blocks[block_size];

int query (int l,int r) {
    int sum = 0;
    int block_l = l / block_size,block_r = r / block_size;
    if (block_l == block_r) {
        for (int i = l; i <= r; ++i) sum += input[i];
    } else {
        int end = (block_l + 1) * block_size - 1;
        for (int i = l; i <= end; ++i) sum += input[i];
        for (int i = block_l + 1; i < block_r; ++i) sum += blocks[i];
        for (int i = block_r * block_size; i <= r; ++i) sum += input[i];
    }
    return sum;
}

void init (int n) {
    for (int i = 0; i < n; ++i) blocks[i / block_size] += input[i];
}

void test () {
    int n = 15000;
    for (int i = 0; i < n; ++i) input[i] = rand() % 15000 + 10;
    init(n);
    int q = 200;
    for (int i = 1; i <= q; ++i) {
        int l = rand() % 15000;
        int r = rand() % 15000;
        if (l > r) continue;
        int sum = 0;
        for (int i = l; i <= r; ++i) sum += input[i];
        assert(sum == query(l,r));
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T = 1;
     //~ cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         int n,q;
         cin >> n >> q;
         for (int i = 0; i < n; ++i) cin >> input[i];
         for (int i = 0; i < n; ++i) blocks[i / block_size] += input[i];
         for (int i = 1; i <= q; ++i) {
             int l,r;
             cin >> l >> r;
             --l,--r;
             cout << query(l,r) << '\n';
         }
     }
     //~ cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}