题目描述

题目要求区间和，为什么我们不把区间平方和以及立方和都求出来呢？

对于k方和，只需要多加几个线段树就好了。

代码解释

代码实现了一个_SegmentTree的线段树类。
构造函数中，需要输入 数组长度n，最高阶数k和初始化数组。

区间修改不需要改变。
区间和，每次多输入一个阶数k。

(暴力枚举) $O(k^2mlogn)$

C++ 代码

#pragma GCC optimize(2)
#include<iostream>
#include<map>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;

const LL N = 100100;

int w[N];

template <class T>
class _SegmentTree {

public:
    struct _node {
        long long l, r;
        T sum, add;
    };

    vector<_node*> tr;
    vector<long long*> coefficients;
    long long* inv; //逆元 
    long long* factor; //系数
    long long* next_factor;
    int degree;
    long long Mod = 998244353;

    _SegmentTree(int n,int k,int* w) {

        factor = new long long[degree+1];
        next_factor = new long long[degree+1];
        degree = k;
        // 求逆元
        inv = new long long[degree + 1];
        inv[1] = 1;
        for (int i = 2;i <= degree;i++) {
            inv[i] = (long long)(Mod - Mod / i) * inv[Mod % i] % Mod;
        }
        // 初始化变量
        for (int i = 0;i <= degree;i++) {
            _node* a;
            if(i==0) a = new _node;
            else a = new _node[4 * n];
            tr.push_back(a);

            long long* b = new long long[i + 1];
            get_factor(b, i);
            coefficients.push_back(b);
        }
        build(1, 1, n, w);
    }


    void get_factor(long long* arr, int len) {
        arr[0] = 1;
        for (int i = 0;i < len;i++) {
            arr[i + 1] = arr[i] * (len - i)% Mod *inv[i + 1]% Mod;
        }
    }

    // 根据 x^n, x^(n-1), ... x , 1 求出(x+d)^n 的值 O(k)
    long long get_next_degree(long long k,long long d) {
        long long p1 = factor[k];
        long long interval = 1;
        for (int i = k - 1;i >= 0;i--) {
            interval *=d;
            p1 +=coefficients[k][i] * interval * factor[i];
        }

        return p1;
    }
    // O(k*k)
    void get_next_vector(long long k, long long d) {
        next_factor[0] = factor[0];
        for (int i = 1;i <= k;i++) {
            next_factor[i] = get_next_degree(i, d);
        }  
    }

    void _pushdown(long long u , long long add_num) {

       // tr[1][u].sum += add_num*(tr[1][u].r - tr[1][u].l+1);
       // tr[1][u].add += add_num;

        factor[0] =tr[degree][u].r - tr[degree][u].l + 1;
        for (int i = 1;i <= degree;i++)
              factor[i]=tr[i][u].sum;


        get_next_vector(degree, add_num);
        for (int i = 1;i <= degree;i++){
            tr[i][u].add += add_num;
            tr[i][u].sum = next_factor[i];
        }
        return;
    }

    long long pushdown(long long u) {

        if (tr[degree][u].add!=0) {

            _pushdown(u << 1, tr[degree][u].add);
            _pushdown(u << 1|1, tr[degree][u].add);

            for (int i = 1;i <= degree;i++)
                tr[i][u].add = 0;
        }
        return 0;
    }

    long long pushup(long long u) {
        for(int i=1;i<=degree;i++)
            tr[i][u].sum = tr[i][u << 1].sum + tr[i][u << 1 | 1].sum;
        return 0;
    }

    void build(int u, int l, int r,int* w) {
        if (l == r) {
            long long num = w[l];
                for (int i = 1;i <= degree;i++) {
                    tr[i][u] = { l,r,num,0 };
                    num = num * w[l];
                }
        }
        else {
            for (int i = 1;i <= degree;i++)
                tr[i][u] = { l,r,0,0};
            int mid = l + r >> 1;
            build(u << 1, l, mid,w);build(u << 1 | 1, mid + 1, r,w);
            pushup(u);
        }
    }

    long long query(long long u, long long l, long long r,long long k) {
        if (k == 0)return (r - l + 1);

        if (tr[k][u].l >= l && tr[k][u].r <= r)return tr[k][u].sum;
        pushdown(u);

        int mid = tr[k][u].l + tr[k][u].r >> 1;
        long long sum = 0;

        if (l <= mid)sum += query(u << 1, l, r,k);
        if (r > mid)sum += query(u << 1 | 1, l, r,k);
        return sum;
    }


    void modify(LL u, LL l, LL r, LL d) {

        if (tr[degree][u].l >= l && tr[degree][u].r <= r) {
            _pushdown(u, d);

        }
        else {  //一定要分类
            pushdown(u);
            int mid = tr[degree][u].l + tr[degree][u] .r >> 1;
            if (l <= mid)modify(u << 1, l, r, d);
            if (r > mid)modify(u << 1 | 1, l, r, d);
            pushup(u);
        }
    }
};





int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    for (int i = 1;i <= n;i++)
        cin >> w[i];

    _SegmentTree<long long> tree1(N,2,w);


    char op;
    int l, r, d;

    for (int i = 0;i < m;i++) {

        cin >> op >> l >> r;
        if (op == 'C')
        {
            cin >> d;
            tree1.modify(1, l, r, d);
        }
        else {

            cout << tree1.query(1, l, r, 1) << endl;

        }



    }
    return 0;
}