1264. 动态求连续区间和题解

题目描述

给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式 第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。第二行包含 n 个整数，表示完整数列。接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。数列从 1 开始计数。 输出格式 输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。 数据范围 1≤n≤100000, 1≤m≤100000， 1≤a≤b≤n, 数据保证在任何时候，数列中所有元素之和均在 int 范围内。 输入样例 10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 0 1 3 0 4 8 1 7 5 0 4 8 输出样例 11 30 35

题解思路

模板题下面分别给出树状数组和线段树做法原理不再给出

代码

树状数组的写法

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
int a[N], tr[N];

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

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) add(i, a[i]);

    while (m -- )
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 0) printf("%d\n", query(y) - query(x - 1));
        else add(x, y);
    }

    return 0;
}

线段树的写法

cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
int w[N]; //记录一下权重

struct Node
{
    int l, r;  //左右区间
    int sum;  //总和
}tr[N * 4];  //记得开 4 倍空间

void pushup(int u)  //利用它的两个儿子来算一下它的当前节点信息
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;  //左儿子 u<<1 ,右儿子 u<<1|1
}

void build(int u, int l, int r)  /*第一个参数，当前节点编号，第二个参数，左边界，第三个参数，右边界*/
{
    if (l == r) tr[u] = {l, r, w[r]}; //如果当前已经是叶节点了，那我们就直接赋值就可以了
    else  //否则的话，说明当前区间长度至少是 2，那么我们需要把当前区间分为左右两个区间，那先要找边界点
    {
        tr[u] = {l, r};  //这里记得赋值一下左右边界的初值
        int mid = l + r >> 1;  //边界的话直接去计算一下 l + r 的下取整
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);  //先递归一下左儿子,然后递归一下右儿子
        pushup(u);  //做完两个儿子之后的话呢 push_up一遍u，更新一下当前节点信息
    }
}

int query(int u, int l, int r)  //查询的过程是从根结点开始往下找对应的一个区间
{
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;    //如果当前区间已经完全被包含了，那么我们直接返回它的值就可以了
    //否则的话我们需要去递归来算
    int mid = tr[u].l + tr[u].r >> 1;  //计算一下我们 当前 区间的中点是多少  
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);  //看一下我们当前区间的中点和左边有没有交集
    if (r > mid) sum += query(u << 1 | 1, l, r);  //看一下我们当前区间的中点和右边有没有交集
    return sum;
}

void modify(int u, int x, int v) //第一个参数也就是当前节点的编号,第二个参数是要修改的位置，第三个参数是要修改的值
{
    if (tr[u].l == tr[u].r) tr[u].sum += v;  //如果当前已经是叶节点了，那我们就直接让他的总和加上 v 就可以了
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;  //看一下 x 是在左半边还是在右半边
        if (x <= mid) modify(u << 1, x, v);  //如果是在左半边，那就找左儿子
        else modify(u << 1 | 1, x, v);  //如果在右半边，那就找右儿子
        pushup(u);  //push_up一遍u，更新一下当前节点信息
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);  /*第一个参数是根节点的下标，根节点是一号点，然后初始区间是 1 到 n */

    int k, a, b;
    while (m -- )
    {
        scanf("%d%d%d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(1, a, b));   //也是传三个参数，第一个的话是根节点的编号 ，第二个的话是我们查询的区间 
        else modify(1, a, b);  //第一个参数是根节点的下标,第二个参数是要修改的位置，第三个参数是要修改的值
    }

    return 0;
}

题目描述 ​

题解思路 ​

代码 ​

树状数组的写法 ​

线段树的写法 ​

题目描述

题解思路

代码

树状数组的写法

线段树的写法