Dynamic Programming + Prefix Sum,Segment Tree Code did not pass even after extreme optimisation
n=sizeof(nums)
m=max_elementComplexity
Time complexity:O(n*m)

Space complexity:O(n*m)
CodeSegment Tree Code for reference
TC: O(nmlog(m))
SC: O(n*m)
n=sizeof(nums)
m=max_element
# Complexity
- Time complexity:O(n*m)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:O(n*m)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#define ll long long
const ll mod = 1e9 + 7;

class Solution {
public:
    int countOfPairs(vector<int>& nums) {

        int n = nums.size();
        vector<vector<ll>> dp(n + 1, vector<ll>(1001, 0));

        for (int i = 0; i < 1001; i++)
            dp[n][i] = 1;

        for (int i = 1; i < 1001; i++) {
            dp[n][i] = (dp[n][i] + dp[n][i - 1]) % mod;
        }

        for (int i = n-1; i >= 0; i--) {
            if (i == 0) {
                int prev1 = 0;
                int prev2 = 1000;

                int X = nums[i];

                int l = max(0, max(X - prev2, prev1));
                int r = min(1000, X);

               

                ll ans = dp[i + 1][r];
                 if (l > 0 && l<=1001)
                    ans = (ans - dp[i + 1][l - 1] + mod) % mod;

                dp[i][prev1] = ans;

                if (prev1 > 0)
                    dp[i][prev1] = (dp[i][prev1] + dp[i][prev1 - 1]) % mod;
            } else {
                for (int prev1 = 0; prev1 <= 1000; prev1++) {
                    int prev2 = nums[i - 1] - prev1;
                    int X = nums[i];

                    int l = max(0, max(X - prev2, prev1));
                    int r = min(1000, X);

                    if(r<l){
                        if(prev1>0)
                        dp[i][prev1]=dp[i][prev1-1];
                        continue;

                    }
                   
                    ll ans = dp[i + 1][r];
                   // if(l>1001) cout<<l<<endl;
                 //   cout<<l<<endl;
                    if (l > 0 && l<=1001)
                    ans = (ans - dp[i + 1][l - 1] + mod) % mod;

                    dp[i][prev1] = ans;

                    if (prev1 > 0)
                        dp[i][prev1] = (dp[i][prev1] + dp[i][prev1 - 1]) % mod;
                }
            }
        }

        return dp[0][0];
    }
};
``````
Segment Tree Code for reference
TC: O(n*m*log(m))
SC: O(n*m)
```
#define ll long long


using namespace std;

const ll MOD = 1e9 + 7;  // Define the modulus

class SegmentTree {
private:
    int n;
    vector<ll> tree;

    void build(const vector<ll>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start] % MOD;  // Ensure values are modulo MOD
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]) % MOD;
        }
    }

    void update(int node, int start, int end, int idx, ll val) {
        if (start == end) {
            tree[node] = val % MOD;  // Store value modulo MOD
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid)
                update(2 * node + 1, start, mid, idx, val);
            else
                update(2 * node + 2, mid + 1, end, idx, val);
            tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]) % MOD;
        }
    }

    ll query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0; // Out of range
        if (l <= start && end <= r) return tree[node]; // Fully inside range
        int mid = (start + end) / 2;
        return (query(2 * node + 1, start, mid, l, r) +
                query(2 * node + 2, mid + 1, end, l, r)) % MOD;
    }

public:
    SegmentTree(const vector<ll>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        build(arr, 0, 0, n - 1);
    }

    void update(int idx, ll val) {
        update(0, 0, n - 1, idx, val);
    }

    ll query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
};


class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        
        int n=nums.size();
        vector<vector<ll>> dp(n+1,vector<ll>(1001,0));

        for(int i=0;i<1001;i++)
        dp[n][i]=1;

        vector<SegmentTree> sgs;

        for(auto i:dp){
            sgs.emplace_back(i);
        }

        for(int i=n-1;i>=0;i--){
            if(i==0){
            int prev1=0;
            int prev2=1000;
             
            int X=nums[i];

            int l=max(0,max(X-prev2,prev1));
            int r=min(1000,X);

            dp[i][prev1]=sgs[i+1].query(l,r);
            sgs[i].update(prev1,dp[i][prev1]);

            }
            else{
                for(int prev1=1000;prev1>=0;prev1--){
                    int prev2= nums[i-1]-prev1;
                    int X=nums[i];

                    int l=max(0,max(X-prev2,prev1));
                    int r=min(1000,X);

                    dp[i][prev1]=sgs[i+1].query(l,r);
                    sgs[i].update(prev1,dp[i][prev1]);
                }
            }
        }

        return dp[0][0];
    }
};
['Array', 'Math', 'Dynamic Programming', 'Segment Tree', 'Prefix Sum', 'C++']