区间和计数（树状数组、fhq treap、cdq & 归并）

using ll = long long;

ll sums[n];
sums[0] = nums[0];

for (int i = 1; i < n; i++)
    sums[i] = sums[i - 1] + nums[i];

map<ll, int> counts; // 统计: 前缀和 => 出现次数

int ans = 0;

// 对每个 x = sums[i]，找右侧已经出现过的 y
for (int i = n - 1; i >= 0; i--) {
    counts[sums[i]]++;

    // 找出 y 的左右界
    ll x = (i == 0 ? 0 : sums[i - 1]);
    ll l = lower + x, r = upper + x;

    auto left = counts.lower_bound(l),
         right = counts.upper_bound(r);

    // 汇总个数
    while (left != right && left != counts.end()) {
        ans += left->second;
        left++;
    }
}

BIT b(N); // 维护计数数组的树状数组

for (int i = n - 1; i >= 0; i--) { // 从后向前
    b.add(sums[i], 1);  // 单点增加, 计数

    ll x = (i == 0 ? 0 : sums[i - 1]); // x
    ll l = lower + x, r = upper + x; // y 的左右界

    int c = b.ask(r) - b.ask(l - 1); // [l, r] 内的 y 的计数
    ans += c;
}

// sums 离散化，用离散化后的数据来代表计数
// 离散化技巧: 也要把 s+lower 和 s+upper 放进去
set<ll> st;
for (auto s : sums) {
    st.insert(s);
    st.insert(s + lower);
    st.insert(s + upper);
}
st.insert(0 + lower);
st.insert(0 + upper);

// 离散化前的数据值 => 映射到具体的大小
// 用树状数组的话，映射到 1 起始的值域
unordered_map<ll, int> mp;
for (auto s : st) mp[s] = mp.size() + 1;

// 后面使用 mp[s] 来和树状数组交互即可

// 返回 <= v 的节点个数
int leqthan(ll v) {
    int x, y;
    split(root, v, x, y);
    int ans = tr[x].size;
    merge(x, y);
    return ans;
}

// cdq 函数用来处理闭区间 [start, end] 上的计数，累加到 ans 上
void cdq(vector<ll>& sums, int start, int end,
        int lower, int upper, int& ans) {
    // TODO
}

// 分治的调用起点
int ans = 0;
cdq(sums, 0, n-1, lower, upper, ans);

void cdq(vector<ll>& sums, int end,
        int lower, int upper, int& ans) {
    if (start >= end) return;
    int mid = (start + end) >> 1;

    // 第 1 种情况，都在左边
    cdq(a, start, mid, lower, upper, ans);
    // 第 2 种情况 TODO
    // 第 3 种情况，都在右边
    cdq(a, mid+1, end, lower, upper, ans);
}

struct P {
    int idx; // 下标
    ll sum; // 前缀和
};

// 按前缀和排序
bool cmp_sum(const P& a, const P& b) { return a.sum < b.sum; }
// 恢复秩序时，按下标排序
bool cmp_idx(const P& a, const P& b) { return a.idx < b.idx; }

void cdq(vector<P>& a, int end,
        int lower, int upper, int& ans) {
    if (start >= end) return;

    int mid = (start + end) >> 1;

    // 两边分别排序
    sort(a.begin() + start, a.begin() + mid + 1, cmp_sum);
    sort(a.begin() + mid + 1, a.begin() + end + 1, cmp_sum);

    // 处理左边
    cdq(a, start, mid, lower, upper, ans);

    // TODO: 计算左边对右边的贡献

    // 恢复右边秩序，并处理右边
    sort(a.begin() + mid + 1, a.begin() + end + 1, cmp_idx);
    cdq(a, mid+1, end, lower, upper, ans);
}

void cdq(vector<P>& a, int start, int end,
        int lower, int upper, int& ans) {
    if (start >= end) return;
    int mid = (start + end) >> 1;

    // 先处理左边
    cdq(a, start, mid, lower, upper, ans);

    // 左边和右边分别排序
    sort(a.begin() + start, a.begin() + mid + 1, cmp_sum);
    sort(a.begin() + mid + 1, a.begin() + end + 1, cmp_sum);

    // 计算左边对右边的贡献
    int cnt1 = count(a, start, end, mid, lower - 1);
    int cnt2 = count(a, start, end, mid, upper);
    ans += cnt2 - cnt1;

    // 恢复右边秩序, 处理右边
    sort(a.begin() + mid + 1, a.begin() + end + 1, cmp_idx);
    cdq(a, mid + 1, end, lower, upper, ans);
}

void dq(vector<ll>& a, int start, int end, int lower, int upper,
        int& ans, vector<ll>& tmp) {
    if (start >= end) return;
    int mid = (start + end) >> 1;

    // 先处理左边, 并排序
    dq(a, start, mid, lower, upper, ans, tmp);

    // 再处理右边, 并排序
    dq(a, mid + 1, end, lower, upper, ans, tmp);

    // 计算左边对右边的贡献, TODO: 和 CDQ 分治第 2 点的处理一样.

    // 合并排序, 注意归并排序是依赖一个临时数组的
    merge(a, start, mid, mid + 1, end, tmp, start);
}