acwing 243. 一个简单的整数问题2 树状数组 线段树

地址 https://www.acwing.com/problem/content/description/244/

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

2、“Q l r”，表示询问 数列中第 l~r 个数的和。

对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行表示M条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

≤N,M≤,

|d|≤,

|A[i]|≤

输入样例：

Q

Q

Q

C

Q

输出样例：

解答

线段树模板  与上一题几乎一摸一样的板子 可以解决

可以说线段树就是解决此类问题的方案  缺点是相对树状数组 代码稍多

 #include <iostream>

 #include <algorithm>

 #include <string>

 using namespace std;

 const int maxn = 1e5 + ;

 int n;

 int a[maxn];

 int q;

 struct node {

     int l, r;

     long long sum, lazy;

     void update(long long x) {

         sum += 1ll * (r - l + )*x;

         lazy += x;

     }

 }tree[maxn*];

 void push_up(int x) {

     tree[x].sum = tree[x << ].sum + tree[x <<  | ].sum;

 }

 void push_down(int x)

 {

     int lazyval = tree[x].lazy;

     if (lazyval) {

         tree[x << ].update(lazyval);

         tree[x <<  | ].update(lazyval);

         tree[x].lazy = ;

     }

 }

 void build(int x, int l, int r) {

     tree[x].l = l; tree[x].r = r;

     tree[x].sum = tree[x].lazy = ;

     if (l == r) {

         tree[x].sum = a[l];

     }

     else {

         int mid = (l + r) / ;

         build(x << , l, mid);

         build(x <<  | , mid + , r);

         push_up(x);

     }

 }

 void update(int x, int l, int r, long long val)

 {

     int L = tree[x].l, R = tree[x].r;

     if (l <= L && R <= r) {

         tree[x].update(val);

     }

     else {

         push_down(x);

         int mid = (L + R) / ;

         if (mid >= l)  update(x << , l, r, val);

         if (r > mid) update(x <<  | , l, r, val);

         push_up(x);

     }

 }

 long long query(int x, int l, int r)

 {

     int L = tree[x].l, R = tree[x].r;

     if (l <= L && R <= r) {

         return tree[x].sum;

     }

     else {

         push_down(x);

         long long ans = ;

         int mid = (L + R) / ;

         if (mid >= l)  ans += query(x << , l, r);

         if (r > mid)  ans += query(x <<  | , l, r);

         push_up(x);

         return ans;

     }

 }

 int main()

 {

     cin >> n >> q;

     for (int i = ; i <= n; i++) {

         cin >> a[i];

     }

     build(, , n);

     for (int i = ; i <= q; i++) {

         string s;

         int l, r, d, q;

         cin >> s;

         if (s == "Q") {

             cin >> l>>r;

             cout << query(, l, r) << endl;

         }

         else {

             cin >> l >> r >> d;

             update(, l, r, d);

         }

     }

     return ;

 }

线段树

线段树的 区间加 区间和查询解决方案 要使用差分数组

// 1111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。

//

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

const int N = ;

typedef long long LL;

int n, m;

int a[N];

LL tree1[N];        //b[i]前缀和  差分数组

LL tree2[N];        //b[i]*i前缀和

int lowbit(int x) {

    return x & -x;

}

void add(LL tr[], int x, LL c) {

    for (int i = x; i <= n; i += lowbit(i))  tr[i] += c;

}

LL sum(LL tr[], int x) {

    LL res = ;

    for(int i = x;i;i-=lowbit(i))  res += tr[i];

    return res;

}

LL prefix_sum(int x) {

    return sum(tree1, x)*(x + ) - sum(tree2, x);

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]);

    for (int i = ; i <= n; i++) {

        int b = a[i] - a[i - ];

        add(tree1, i, (LL)b);

        add(tree2, i, (LL)b*i);

    }

    while (m--) {

        char op[];

        int l, r, d;

        scanf("%s%d%d", op, &l, &r);

        if (*op == 'Q') {

            printf("%lld\n",prefix_sum(r)-prefix_sum(l-));

        }

        else {

            scanf("%d", &d);

            //a[l]+=d

            add(tree1, l, d);

            add(tree2, l, l*d);

            // a[r+1] -= d

            add(tree1, r + , -d);

            add(tree2, r + , (r + )*-d);

        }

    }

    return ;

}

acwing 243. 一个简单的整数问题2 树状数组 线段树的相关教程结束。