この問題は俗にimos法と呼ばれる、累積和の逆操作を用いることで高速に求めることができます。

累積和は数列同士の和を保ちます。つまり、「数列 \(A\) の累積和と数列 \(B\) の累積和を足した数列」は「数列 \(A\) と数列 \(B\) を足した数列の累積和」になります。

                  差分 ←      → 累積和
A   0  1  0  0  1  0  0        0  0  1  1  1  2  2  2 
B   0  0 -1  0  0  2  0        0  0  0 -1 -1 -1  1  1
A+B 0  1 -1  0  1  2  0        0  0  1  0  0  1  3  3

また「ある区間の要素が \(1\) でそれ以外は全て \(0\)」という数列に対し、累積和の逆操作を行うと「\(1\) と \(-1\) が \(1\) 個ずつで他は全て \(0\) 」という数列になります。

    0   1   0   0   0  -1   0   0
            累積和↓   ↑差分
  0   0   1   1   1   1   0   0   0

よって「 \((0,\dots,0,1,\dots,1,0,\dots,0)\) の形の数列 \(M\) 個の和」は「\((0,\dots,0,1,0,\dots,0,-1,0,\dots,0)\) の形の数列 \(M\) 個の和の累積和」となり、これは \(O(N+M)\) で求めることができます。

このように、累積和の逆操作を用いて計算を高速化する手法全般をimos法と呼びます。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<int>c(n+1);
  for(int i=0; i<m; i++){
    int l, r;
    cin >> l >> r;
    c[l-1]++;
    c[r]--;
  }
  for(int i=0; i<n; i++){
    c[i+1] += c[i];
  }

  for(int i=0; i<n; i++){
    cout << (long long) a[i] * c[i];
    if(i == n-1){
      cout << endl;
    }else{
      cout << ' ';
    }
  }
}

実装例 (Python)

N, M = map(int, input().split())
A = list(map(int, input().split()))
C = [0] * (N+1)
for _ in range(M):
  L, R = map(int, input().split())
  C[L-1] += 1
  C[R] -= 1

for i in range(N):
  C[i+1] += C[i]

P = [A[i] * C[i] for i in range(N)]
print(*P)