Recently, I was doing a LeetCode problem (I know, I know what you are thinking ;( ), it was LC 2281: S, [it was LC 2281: Sum of Total Strength of Wizards](https://leetcode.com/problems/sum -of T-total S-strength -of W-wizards/description/)), and I stumbled upon a subproblem that I found genuinely interesting.↵
↵
The problem basically boiled down to this: **You are given $q$ queries, each with an $L$ and $R$. For each query, you need to find the sum of all subarrays entirely contained within the range $[L, R]$, and you have to answer each query efficiently.**↵
↵
If we write it out as a brute force, it's just three nasty nested `for` loops:↵
$$q(L, R) = \sum_{i=L}^{R} \sum_{j=i}^{R} \sum_{k=i}^{j} a_k$$↵
↵
Say you only had to find $\sum_{i=L}^{R} a_i$. This is easy with standard prefix sum array. You just define $P[x] = \sum_{i=0}^{x-1} a_i$, which answer the queries in $O(1)$ time: $P[R+1] - P[L]$.↵
↵
But what do we do when we have multiple summations? Can we still answer this in $O(1)$?↵
*Spoiler: Yes. We just need to go deeper.*↵
↵
*(Side note: This logic can actually be generalized. If you are summing up $f(i) \times a_i$ where $f(x)$ is some ugly huge polynomial of degree $d$, you can still answer it in $O(d)$ time. But the calculations keep getting uglier, unless polynoimal is very simple, so i am not doing that)*↵
↵
---↵
↵
### Unpacking the summations↵
↵
The logic is simple: we just keep defining new prefix sum arrays to collapse the loops from the inside out. The math might look daunting at first glance, but it's very easy to follow (and to do off by one errors) if we just take it one step at a time.↵
↵
Let's evaluate the innermost loop first. We know that $\sum_{k=i}^{j} a_k = P[j+1] - P[i]$.↵
↵
So our query becomes:↵
$$q(L, R) = \sum_{i=L}^{R} \sum_{j=i}^{R} (P[j+1] - P[i])$$↵
↵
Distribute the summation:↵
$$q(L, R) = \sum_{i=L}^{R} \left( \sum_{j=i}^{R} P[j+1] - \sum_{j=i}^{R} P[i] \right)$$↵
↵
#### First term: $\sum_{j=i}^{R} P[j+1]$↵
↵
To solve this without a loop, let's just make a prefix sum array **of our prefix sum array $P$**. Let's call it $PP$.↵
Using the standard prefix sum logic on $P$, this simply evaluates to:↵
↵
$$\sum_{j=i}^{R} P[j+1] = PP[R+2] - PP[i+1]$$↵
↵
#### Second term: $\sum_{j=i}^{R} P[i]$↵
↵
Notice that $P[i]$ does not depend on $j$ at all! It's effectively a constant in the inner loop. How many times are we adding it? Exactly $(R - i + 1)$ times. So:↵
$$\sum_{j=i}^{R} P[i] = (R - i + 1)P[i]$$↵
↵
#### Putting back together:↵
↵
Substitute these two pieces back into our outer loop:↵
$$q(L, R) = \sum_{i=L}^{R} \left( PP[R+2] - PP[i+1] - (R - i + 1)P[i] \right)$$↵
↵
Now, let's break this remaining outer loop into three separate terms:↵
↵
1. **Term 1:** $\sum_{i=L}^{R} PP[R+2]$↵
2. **Term 2:** $\sum_{i=L}^{R} PP[i+1]$↵
3. **Term 3:** $\sum_{i=L}^{R} (R - i + 1)P[i]$↵
↵
Lets do them one by one.↵
↵
**Term 1:** $PP[R+2]$ does not depend on $i$. It's a constant.↵
$$ \sum_{i=L}^{R} PP[R+2] = (R - L + 1) \cdot PP[R+2] $$↵
**Term 2:** We need a sum of ranges on $PP$. The idea is again the same. We spin up *another* prefix sum array, this time for $PP$. Let's call it $PPP$.↵
$$ \sum_{i=L}^{R} PP[i+1] = PPP[R+2] - PPP[L+1] $$↵
**Term 3:** Expanding the coefficient $(R - i + 1)$ into $(R + 1) - i$:↵
$$ \sum_{i=L}^{R} (R - i + 1)P[i] = (R+1) \sum_{i=L}^{R} P[i] - \sum_{i=L}^{R} i \cdot P[i] $$↵
↵
We already have the prefix array for $P$ (which is $PP$), so the first half is just $(R+1)(PP[R+1] - PP[L])$.↵
For the second half, we define one last prefix sum array $W$ to handle the weight $i$:↵
↵
$$W[x] = \sum_{k=0}^{x-1} k \cdot P[k]$$↵
So the second half becomes $W[R+1] - W[L]$.↵
↵
### Final Result↵
↵
Combine everything, being careful with the minus signs, and you get this beautiful (and very long), $O(1)$ constant-time query formula:↵
↵
$$q(L, R) = (R - L + 1)PP[R+2] - \left(PPP[R+2] - PPP[L+1]\right) - (R+1)\left(PP[R+1] - PP[L]\right) + \left(W[R+1] - W[L]\right)$$↵
↵
---↵
↵
### Code↵
↵
*(Note: I am not worrying about overflows for brevity!)*↵
↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
vector<long long> P, PP, PPP, W;↵
↵
long long query(int L, int R) {↵
return 1LL * (R - L + 1) * PP[R + 2]↵
- (PPP[R + 2] - PPP[L + 1])↵
- 1LL * (R + 1) * (PP[R + 1] - PP[L])↵
+ (W[R + 1] - W[L]);↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int n, q;↵
if (!(cin >> n >> q)) return 0;↵
↵
vector<int> a(n);↵
for(int& x : a) cin >> x;↵
↵
P.assign(n + 1, 0); // prefix of a↵
PP.assign(n + 2, 0); // prefix of P↵
PPP.assign(n + 3, 0); // prefix of PP↵
W.assign(n + 1, 0); // weighted prefix: i * P[i]↵
↵
// Build the prefixes↵
for (int i = 0; i < n; i++)↵
P[i + 1] = P[i] + a[i];↵
↵
for (int i = 0; i <= n; i++)↵
PP[i + 1] = PP[i] + P[i];↵
↵
for (int i = 0; i <= n + 1; i++)↵
PPP[i + 1] = PPP[i] + PP[i];↵
↵
for (int i = 0; i <= n; i++)↵
W[i + 1] = W[i] + 1LL * i * P[i];↵
↵
// Answer queries in O(1)↵
while(q--) {↵
int l, r;↵
cin >> l >> r;↵
cout << query(l, r) << "\n";↵
}↵
return 0;↵
}↵
```↵
↵
And there you go! I hope this helps anyone who runs into a similar subproblem.↵
Peace out!
↵
The problem basically boiled down to this: **You are given $q$ queries, each with an $L$ and $R$. For each query, you need to find the sum of all subarrays entirely contained within the range $[L, R]$, and you have to answer each query efficiently.**↵
↵
If we write it out as a brute force, it's just three nasty nested `for` loops:↵
$$q(L, R) = \sum_{i=L}^{R} \sum_{j=i}^{R} \sum_{k=i}^{j} a_k$$↵
↵
Say you only had to find $\sum_{i=L}^{R} a_i$. This is easy with standard prefix sum array. You just define $P[x] = \sum_{i=0}^{x-1} a_i$, which answer the queries in $O(1)$ time: $P[R+1] - P[L]$.↵
↵
But what do we do when we have multiple summations? Can we still answer this in $O(1)$?↵
*Spoiler: Yes. We just need to go deeper.*↵
↵
*(Side note: This logic can actually be generalized. If you are summing up $f(i) \times a_i$ where $f(x)$ is some ugly huge polynomial of degree $d$, you can still answer it in $O(d)$ time. But the calculations keep getting uglier, unless polynoimal is very simple, so i am not doing that)*↵
↵
---↵
↵
### Unpacking the summations↵
↵
The logic is simple: we just keep defining new prefix sum arrays to collapse the loops from the inside out. The math might look daunting at first glance, but it's very easy to follow (and to do off by one errors) if we just take it one step at a time.↵
↵
Let's evaluate the innermost loop first. We know that $\sum_{k=i}^{j} a_k = P[j+1] - P[i]$.↵
↵
So our query becomes:↵
$$q(L, R) = \sum_{i=L}^{R} \sum_{j=i}^{R} (P[j+1] - P[i])$$↵
↵
Distribute the summation:↵
$$q(L, R) = \sum_{i=L}^{R} \left( \sum_{j=i}^{R} P[j+1] - \sum_{j=i}^{R} P[i] \right)$$↵
↵
#### First term: $\sum_{j=i}^{R} P[j+1]$↵
↵
To solve this without a loop, let's just make a prefix sum array **of our prefix sum array $P$**. Let's call it $PP$.↵
Using the standard prefix sum logic on $P$, this simply evaluates to:↵
↵
$$\sum_{j=i}^{R} P[j+1] = PP[R+2] - PP[i+1]$$↵
↵
#### Second term: $\sum_{j=i}^{R} P[i]$↵
↵
Notice that $P[i]$ does not depend on $j$ at all! It's effectively a constant in the inner loop. How many times are we adding it? Exactly $(R - i + 1)$ times. So:↵
$$\sum_{j=i}^{R} P[i] = (R - i + 1)P[i]$$↵
↵
#### Putting back together:↵
↵
Substitute these two pieces back into our outer loop:↵
$$q(L, R) = \sum_{i=L}^{R} \left( PP[R+2] - PP[i+1] - (R - i + 1)P[i] \right)$$↵
↵
Now, let's break this remaining outer loop into three separate terms:↵
↵
1. **Term 1:** $\sum_{i=L}^{R} PP[R+2]$↵
2. **Term 2:** $\sum_{i=L}^{R} PP[i+1]$↵
3. **Term 3:** $\sum_{i=L}^{R} (R - i + 1)P[i]$↵
↵
Lets do them one by one.↵
↵
**Term 1:** $PP[R+2]$ does not depend on $i$. It's a constant.↵
$$ \sum_{i=L}^{R} PP[R+2] = (R - L + 1) \cdot PP[R+2] $$↵
**Term 2:** We need a sum of ranges on $PP$. The idea is again the same. We spin up *another* prefix sum array, this time for $PP$. Let's call it $PPP$.↵
$$ \sum_{i=L}^{R} PP[i+1] = PPP[R+2] - PPP[L+1] $$↵
**Term 3:** Expanding the coefficient $(R - i + 1)$ into $(R + 1) - i$:↵
$$ \sum_{i=L}^{R} (R - i + 1)P[i] = (R+1) \sum_{i=L}^{R} P[i] - \sum_{i=L}^{R} i \cdot P[i] $$↵
↵
We already have the prefix array for $P$ (which is $PP$), so the first half is just $(R+1)(PP[R+1] - PP[L])$.↵
For the second half, we define one last prefix sum array $W$ to handle the weight $i$:↵
↵
$$W[x] = \sum_{k=0}^{x-1} k \cdot P[k]$$↵
So the second half becomes $W[R+1] - W[L]$.↵
↵
### Final Result↵
↵
Combine everything, being careful with the minus signs, and you get this beautiful (and very long), $O(1)$ constant-time query formula:↵
↵
$$q(L, R) = (R - L + 1)PP[R+2] - \left(PPP[R+2] - PPP[L+1]\right) - (R+1)\left(PP[R+1] - PP[L]\right) + \left(W[R+1] - W[L]\right)$$↵
↵
---↵
↵
### Code↵
↵
*(Note: I am not worrying about overflows for brevity!)*↵
↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
vector<long long> P, PP, PPP, W;↵
↵
long long query(int L, int R) {↵
return 1LL * (R - L + 1) * PP[R + 2]↵
- (PPP[R + 2] - PPP[L + 1])↵
- 1LL * (R + 1) * (PP[R + 1] - PP[L])↵
+ (W[R + 1] - W[L]);↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
int n, q;↵
if (!(cin >> n >> q)) return 0;↵
↵
vector<int> a(n);↵
for(int& x : a) cin >> x;↵
↵
P.assign(n + 1, 0); // prefix of a↵
PP.assign(n + 2, 0); // prefix of P↵
PPP.assign(n + 3, 0); // prefix of PP↵
W.assign(n + 1, 0); // weighted prefix: i * P[i]↵
↵
// Build the prefixes↵
for (int i = 0; i < n; i++)↵
P[i + 1] = P[i] + a[i];↵
↵
for (int i = 0; i <= n; i++)↵
PP[i + 1] = PP[i] + P[i];↵
↵
for (int i = 0; i <= n + 1; i++)↵
PPP[i + 1] = PPP[i] + PP[i];↵
↵
for (int i = 0; i <= n; i++)↵
W[i + 1] = W[i] + 1LL * i * P[i];↵
↵
// Answer queries in O(1)↵
while(q--) {↵
int l, r;↵
cin >> l >> r;↵
cout << query(l, r) << "\n";↵
}↵
return 0;↵
}↵
```↵
↵
And there you go! I hope this helps anyone who runs into a similar subproblem.↵
Peace out!
