1264 动态求连续区间和（线段树模板-无懒标记）

拼搏现实的明天。 2022-09-03 13:12 143阅读 0赞

**1. 问题描述：**

给定 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

**输入样例：**

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

来源：[https://www.acwing.com/problem/content/1266/][https_www.acwing.com_problem_content_1266]

**2. 思路分析：**

① 分析题目可以知道题目主要涉及两个操作，第一个操作是**单点修改**，也即将区间中的某一个数修改为另外一个数（修改为一个数字或者某个数加上一个数字），第二个操作是**区间求和**，对于区间单点修改操作比较频繁并且需要求解区间和操作的题目我们一般考虑树状数组或者**线段树**这两种数据结构来解决，对于这道题目来说可以使用树状数组和线段树进行求解，而且我们需要遵循的一个原则是能够使用树状数组解决就使用树状数组解决，当不能够使用树状数组解决的时候那么我们使用线段树来解决（树状数组比较快一点），但是树状数组只支持单点修改与区间求和操作，使用范围比较局限，而线段树可以支持树状数组的所有操作，并且能够解决树状数组不支持的操作，线段树可以求解区间的最大值，染色之后求面积，最大连续子段和等区间动态修改与查询的相关问题，使用范围比较广，但是树状数组对于同样可以解决的问题的前提下比线段树的性能更好，各有自己的优缺点吧，下面使用线段树来解决这道单点修改与区间求和的模板题。

② 一般常用的线段树有两种，第一种是不带懒标记的线段树，第二种是带有懒标记的线段树，不带懒标记的线段树比较简单一点，带有懒标记的线段树会难一点，对于这道题目来说只是涉及到单点修改与区间求和的操作，所以我们可以使用不带懒标记的线段树解决即可。线段树的原理比树状数组要好理解一点，本质上是一棵二叉树（除了第一层之外是完全二叉树），下面以\[1，7\]作为一个例子说明线段树的原理：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

求解区间和的不带懒标记的线段树主要有四个操作，分别对应下面四个函数：

*  void pushup（int u）； 将左右孩子节点的和传递到当前的根节点（更新操作）
 *  void build(int u，nt l， int r)；创建以当前的u作为根节点，区间\[l, r\]的线段树的线段树结构，创建线段树的时候递归创建左右两边的区间，并且创建好了当前左右两边的区间之后那么需要将子节点的区间和更新到当前的根节点的和，左右两个区间的分界点为l + r >> 1，左边的区间为\[l， mid\]，右边的区间为\[mid + 1，r\]
 *  void modify(int u， int x， int v)；单点修改操作，当前的根节点为u，在x这个位置上加上v，在更新的时候使用递归找到更新的位置（根据当前根节点u维护的区间\[l，r\]的中点mid与x的大小关系判断更新的区间在哪一边），并且在递归更新结束之后需要更新所有包含位置x的区间和
 *  void query(int u，int l，int r)；区间和查询操作，当前的根节点为u，查询区间\[l，r\]的区间和，在查询的时候当前根节点u包含的区间包含在\[l ,r\]那么直接返回当前根节点对应的区间和即可，否则需要根据当前根节点的区间中点与l，r的关系计算区间和即可。

线段树的节点的数目我们可以设置成区间长度的4倍，这是一个经验值。创建线段树其实是一个递归的过程，我们可以递归创建以当前根节点的左右区间，左右区间的分界点为mid，其中mid = l + r >> 1，也即区间中点，左边的区间为\[l, mid\]，右边的区间为\[mid + 1, r\]，当前区间的长度为1时候递归创建就结束了，并且在递归创建左右区间的过程中需要更新每一个根节点表示的区间和。上面四个函数大部分都涉及到了递归更新的操作，递归返回到上一层的时候由下往上进行更新，与树状数组更新的过程是类似的（核心是递归修改的过程理解好递归的过程之后那么就比较容易理解线段树的相关操作了，上==>下，下==>上）。

**3. 代码如下：**

**c++代码：**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100010;
    
    int n, m;
    int w[N];
    struct Node
    {
        int l, r;
        int sum;
    }tr[N * 4];
    
    void pushup(int u)
    {
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    }
    
    void build(int u, int l, int r)
    {
        if (l == r) tr[u] = {l, r, w[r]};
        else
        {
            tr[u] = {l, r};
            int mid = l + r >> 1;
            build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }
    
    int query(int u, int l, int r)
    {
        if (tr[u].l >= 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;
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
        build(1, 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;
    }

**java代码：**

import java.util.Scanner;
    public class Main {
        static Tree tr[];
        static int nums[];
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int m = sc.nextInt();
            // 声明对象数组, 线段树需要声明4n个节点即可
            tr = new Tree[4 * n];
            nums = new int[n + 1];
            for (int i = 1; i <= n; ++i){
                nums[i] = sc.nextInt();
            }
            for (int i = 1; i < 4 * n; ++i) {
                tr[i] = new Tree();
            }
            build(1, 1, n);
            while (m-- > 0){
                int k, a, b;
                k = sc.nextInt();
                a = sc.nextInt();
                b = sc.nextInt();
                if (k == 0){
                    int t = query(1, a, b);
                    System.out.println(t);
                }else {
                    modify(1, a, b);
                }
            }
        }
    
        // 前缀和信息由子节点传递到父节点
        public static void pushup(int u){
            tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
        }
    
        // 创建线段树节点的操作
        public static void build(int u, int l, int r){
            if (l == r){
                tr[u].l = tr[u].r = l;
                tr[u].s = nums[l];
            }else {
                tr[u].l = l;
                tr[u].r = r;
                int mid = l + r >> 1;
                // 递归创建左右两边的线段树
                build(u << 1, l, mid);
                build(u << 1 | 1, mid + 1, r);
                // 更新当前根节点的区间和, 更新的时候从根节点的和往上传递
                pushup(u);
            }
        }
    
        // 单点修改
        public static void modify(int u, int x, int v){
            if (tr[u].l == tr[u].r){
                tr[u].s += v;
            }else {
                int mid = tr[u].l + tr[u].r >> 1;
                if (x <= mid){
                    //当前修改的数在根节点的左边
                    modify(u << 1, x, v);
                }else {
                    //当前修改的数在根节点的右边
                    modify(u << 1 | 1, x, v);
                }
                // 递归修改结束之后由子节点修改的信息传递到父节点
                pushup(u);
            }
        }
    
        //查询操作, 根节点为u, 查询区间和[l, r]
        public static int query(int u, int l, int r){
            if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
            int mid = tr[u].l + tr[u].r >> 1;
            int s = 0;
            if (mid >= l){
                s = query(u << 1, l, r);
            }
            if (mid < r){
                s += query(u << 1 | 1, l, r);
            }
            return s;
        }
    
        // 内部类表示线段树的每一个节点
        public static class Tree{
            int l, r, s;
        }
    }

**python代码（超时，过了6个测试用例，最后一个10w的数据没有过）：**

from typing import List
    
    
    class Tree:
        def __init__(self, l, r, s):
            self.l = l
            self.r = r
            self.s = s
    
    
    class Solution:
        tr = None
    
        def init(self, n: int):
            # 初始化线段树, 下面的Tree(0, 0, 0)相当于是c++中的结构体
            self.tr = [Tree(0, 0, 0) for i in range(n * 4)]
    
        # 将孩子节点的和往父节点上传
        def pushup(self, u: int):
            self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s
    
        # 创建线段树, 维护线段树的每一个点
        def build(self, u: int, l: int, r: int, w: List[int]):
            tr = self.tr
            if l == r:
                tr[u].l = tr[u].r = l
                tr[u].s = w[r]
            else:
                tr[u].l = l
                tr[u].r = r
                mid = l + r >> 1
                self.build(u << 1, l, mid, w)
                self.build(u << 1 | 1, mid + 1, r, w)
                # 维护区间和, 由孩子节点往上传
                self.pushup(u)
    
        # 查询区间[l, r]的区间和, u为当前的根节点
        def query(self, u: int, l: int, r: int):
            tr = self.tr
            if tr[u].l >= l and self.tr[u].r <= r: return tr[u].s
            mid = tr[u].l + tr[u].r >> 1
            s = 0
            if mid >= l:
                s = self.query(u << 1, l, r)
            if mid < r:
                s += self.query(u << 1 | 1, l, r)
            return s
    
        # 单点修改, 当前的根节点是u, 在x的位置上加上v
        def modify(self, u: int, x: int, v: int):
            tr = self.tr
            if tr[u].l == tr[u].r:
                tr[u].s += v
            else:
                mid = tr[u].l + tr[u].r >> 1
                if x <= mid:
                    self.modify(u << 1, x, v)
                else:
                    self.modify(u << 1 | 1, x, v)
                self.pushup(u)
    
    
    if __name__ == '__main__':
        obj = Solution()
        n, m = map(int, input().split())
        obj.init(n)
        nums = list(map(int, input().split()))
        # 为了下标从1开始所以所以需要需要往nums的最前面插入一个数
        nums.insert(0, 0)
        obj.build(1, 1, n, nums)
        while m > 0:
            k, a, b = map(int, input().split())
            # k = 0表示求解[a, b]的和, k = 1的时候表示第a个数加上b
            if k == 0:
                t = obj.query(1, a, b)
                print(t)
            else:
                obj.modify(1, a, b)
            m -= 1

[https_www.acwing.com_problem_content_1266]: https://www.acwing.com/problem/content/1266/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/42a30f0a12af4e668b4427a88fc14b5a.png