公式解説と本質的に同じかもしれませんが、形式的冪級数を経由した考察を紹介します。

この解説では、\(A, B\) の添字は \(0\)-indexed であるとし（\(P\) の添字は \(1\)-indexed のままとします）、クエリでは半開区間 \([l, r)\) に加算するものとします。

数列 \((B_i, B_{i+1}, \dots)\) の母関数を \(\displaystyle \mathcal B_i(x) := \sum_{j\geq0} B_{i+j} x^j\) と書くことにします。\(\displaystyle \mathcal Q(x) := 1 - \sum_{i=1}^K P_i x^i\) とすると、ある \(K\) 次未満の多項式 \(\mathcal S_i(x)\) が存在して \(\mathcal B_i(x) = \dfrac{\mathcal S_i(x)}{\mathcal Q(x)}\) と書けることがよく知られています（この事実については、たとえば [多項式・形式的べき級数]（３）線形漸化式と形式的べき級数 - maspyのHP などを参照してください）。

これを踏まえると、本問の操作は、\(x^l \mathcal B_0(x) - x^r \mathcal B_{r-l}(x) = \dfrac{x^l \mathcal S_0(x) - x^r \mathcal S_{r-l}(x)}{\mathcal Q(x)}\) を加算することと解釈できます。\(\mathcal B_i(x)\) や \(\mathcal S_i(x)\) はクエリによって異なり、\(\mathcal Q(x)\) はクエリ間で共通であることに注意してください。

\(\mathcal Q(x)\) で割るのは最後に \(O(NK)\) 時間で行えるので、\(x^l \mathcal S_0(x) -x^r \mathcal S_{r-l}(x)\) の加算ができればよいです。\(\mathcal S_i(x)\) は \(K\) 次未満であるため、\(\mathcal S_0(x), \mathcal S_{r-l}(x)\) が求められていれば、加算処理は \(O(K)\) 時間で可能です。

\(\mathcal S_t(x)\) の求め方を考えます。\(\mathcal S_t(x) = \mathcal Q(x) \mathcal B_t(x)\) であるので、\(\mathcal B_t(x)\) を \(K-1\) 次まで求められれば（つまり \(B_t, \dots, B_{t+K-1}\) を求められれば）、\(O(K^2)\) 時間で求められます。前計算として \(\displaystyle \mathcal H(x) := \dfrac{1}{\mathcal Q(x)}\) を \(N + K\) 次まで求めておくと（これは \(O((N+K)K)\) 時間で可能です）、\(\displaystyle B_i = [x^i] \mathcal B_0(x) = [x^i] \mathcal S_0(x) \mathcal H(x) = \sum_{j=0}^{K-1} [x^j] \mathcal S_0(x) [x^{i-j}] \mathcal H(x)\) を用いて \(B_i\) を \(O(K)\) 時間で求められるため、\(\mathcal B_t(x)\) は \(O(K^2)\) 時間で求められます。

以上より、問題を全体 \(O(NK + QK^2)\) 時間で解けます。

余談：これは imos 法の一般化と捉えられます。通常の区間加算をする imos 法は、\(\mathcal Q(x) = 1 - x\) の場合です。

類題：https://yukicoder.me/problems/no/1172 （線形漸化的数列の最初の \(K\) 項もクエリ間で共通である場合です。この場合は、\(\mathcal S_0, \mathcal S_1, \mathcal S_2, \dots\) をこの順に求めていくことができ、全体 \(O((N+Q)K)\) 時間で解けます。）