<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

树状数组

说实话一开始我在树状数组部分见到它，是有点意外的，在我看来它就是裸的线段树问题
不过既然出现在树状数组部分了那就说明可以用树状数组解决，稍作了解之后，在此给各位介绍

问题中的两个需求，目标都是区段整体，因此需要同时用上前缀和序列以及差分序列，那么问题的关键就在于，用什么方式可以从差分序列直接越级，得到前缀和序列呢？
先来看如何用差分序列$dif$得到原序列$arr$：
$arr[0] = dif[0]$
$arr[1] = dif[0] + dif[1]$
$arr[2] = dif[0] + dif[1] + dif[2]$
......
$arr[n] = dif[0] + dif[1] + dif[2] + … + dif[n]$

然后用$arr$来得出用$dif$表示的前缀和序列$prs$：
$prs[0] = dif[0]$
$prs[1] = 2\*dif[0] + dif[1]$
$prs[2] = 3\*dif[0] + 2\*dif[1] + dif[2]$
......
$prs[n-1] = n\*dif[0] + (n-1)\*dif[1] + (n-2)\*dif[2] + … + dif[n-1]$
$prs[n] = (n+1)\*dif[0] + n\*dif[1] + (n-1)\*dif[2] + … + 2\*dif[n-1] + dif[n]$

由于$dif[0]$和$arr[0]$都是0，因此不难推导出关键公式：
$$prs[k] = \Sigma_{i=1}^k(dif[i]\*(k-i+1)) = (k+1)\*\Sigma_{i=1}^kdif[i] - \Sigma_{i=1}^k(i\*dif[i])$$
其中包含的两个求和项，用两条树状数组存放，$\Sigma_{i=1}^kdif[i]$跟上一个问题一样用base存放，另一项$\Sigma_{i=1}^k(i\*dif[i])$用第二条树状数组mul存放（不太清楚它的实际含义是啥，由于乘了个i，就起名为mul），更新的时候base和mul同时更新，求长度为x的树状数组前缀和的时候按照上面给出的关键公式，二进制划分x后对每个i累加$(x+1)*base[i] - mul[i]$，查询的区段整体累加和就是树状数组两端前缀和之差

本题解主要介绍的是树状数组，但线段树类仍然会另附最后

C++ 代码

树状数组类：

class BinaryIndexedTree {
private:
    int length = 0;
    /*
    * base[x]就是差分序列dif长度为x的前缀和
    * mul[x]对应着序列{i*dif[i]}长度为x的前缀和
    */
    vector<ll> arr, base, mul;

    int lowbit(int x) {
        return x & -x;
    }

    //同时更新base和mul
    //base加上x，相同位置的mul要加上id*x，之后按照前缀和的规律往后推
    void _update(int id, ll x) {
        for (int i = id; i <= length; i += lowbit(i)) {
            base[i] += x;
            mul[i] += (id * x);
        }
    }

    //参照上面给出的公式，不难得出此函数的实现
    ll preSum(int x) {
        ll ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans += (x + 1) * base[i] - mul[i];
        }
        return ans;
    }
public:
    BinaryIndexedTree(int n) {
        length = n;
        arr.resize(n + 2);
        base.resize(n + 2);
        mul.resize(n + 2);
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            _update(i, arr[i] - arr[i - 1]);
        }
    }

    void update(int l, int r, ll d) {
        _update(l, d);
        _update(r + 1, -d);
    }

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

线段树类：（二叉链表存储法，看个乐叭）

struct Node {
    int start, finish;
    ll sum = 0, offset = 0;
    Node* left = nullptr, * right = nullptr;
    Node() :start(0), finish(0) {}
    Node(int l, int r) :start(l), finish(r) {}
};

class SegmentTree {
private:
    Node* root;
    ll* arr;
    int len;

    void buildTree(Node* node, int l, int r) {
        if (l == r) {
            node->sum += arr[l];
            return;
        }
        int m = (l + r) / 2;
        if(!node->left) node->left = new Node(l, m);
        if(!node->right) node->right = new Node(m + 1, r);
        buildTree(node->left, l, m);
        buildTree(node->right, m + 1, r);
        pushUp(node);
    }

    void pushDown(Node* node) {
        if (node->offset != 0) {
            Node* lc = node->left, * rc = node->right;
            lc->offset += node->offset;
            rc->offset += node->offset;
            lc->sum += node->offset * (lc->finish - lc->start + 1);
            rc->sum += node->offset * (rc->finish - rc->start + 1);
            node->offset = 0;
        }
    }

    void pushUp(Node* node) {
        node->sum = node->left->sum + node->right->sum;
    }

    void _update(Node* node, int l, int r, ll k) {
        if (l <= node->start && r >= node->finish) {
            node->sum += k * (node->finish - node->start + 1);
            node->offset += k;
            return;
        }
        pushDown(node);
        int m = (node->start + node->finish) / 2;
        if (l <= m) _update(node->left, l, r, k);
        if (r > m) _update(node->right, l, r, k);
        pushUp(node);
    }

    ll _sum(Node* node, int l, int r) {
        if (l <= node->start && r >= node->finish) return node->sum;
        pushDown(node);
        int m = (node->start + node->finish) / 2;
        ll ans = 0;
        if (l <= m) ans += _sum(node->left, l, r);
        if (r > m) ans += _sum(node->right, l, r);
        return ans;
    }

    void deleteNode(Node* node) {
        if (node == nullptr) return;
        deleteNode(node->left);
        deleteNode(node->right);
        delete node;
    }
public:
    SegmentTree(int n) {
        len = n;
        arr = new ll[n + 1];
        for (int i = 1; i <= n; i++) cin >> arr[i];
        root = new Node(1, n);
        buildTree(root, 1, n);
    }

    void update(int l, int r, ll k) {
        _update(root, l, r, k);
    }

    ll query(int l, int r) {
        return _sum(root, l, r);
    }

    ~SegmentTree() {
        deleteNode(root);
    }
};