动态求连续区间和

一时失言乱红尘 2024-03-29 15:22 80阅读 0赞

## 动态求连续区间和 ##

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

**算法思路**  
![在这里插入图片描述][f5e4074b85844d62a742e0a0ccb3bd70.png]  
1、lowbit(x):返回x的最后一位1

2、add(x,v):在x位置加上v，并将后面相关联的位置也加上v

3、query(x):询问x的前缀和

### 具体代码 ###

**C++**

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 1e5 + 10;
    int n, m;
    int w[N];
    struct Node{
          // 这个Node的含义为区间[l, r]的sum值是多少 线段树的本质就是一个二叉树 所以后面的所有操作本质就是二叉树的那一套
        int l, r;
        int sum;
    }tr[4 * N];
    
    void push_up(int u) // 通过左右孩子计算父亲的值的函数
    {
         
        tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;  // 父节点的值 等于左右孩子的值相加 u << 1 相当于 u * 2；
    }
    void build(int u, int l, int r) // 建立线段树的函数 第一个参数为当前结点的编号，第二个参数为左边界，第三个参数为右边界
    {
        
        if (l == r) tr[u] = {
        l, r, w[r]}; // 如果当前结点已经是叶子节点了 那么就可以直接把权值赋值给这个 线段树上面的结点了
        else  // 如果当前区间的左右边界不相同 说明当前区间的长度至少是2（这里的理解可以通过看线段树的图来理解，线段树是一个大区间不断分成一个一个的小区间）
        // 直到分到不能再分为止 如果这个区间的长度不小于2 那么这个区间的左右边界 就不相等 那么这个区间就可以继续分
        {
        
            tr[u] = {
        l, r};  // 先对u这个结点的左右边界赋值一下 规定这个u结点表示的区间范围
            int mid = l + r >> 1;
            // 把结点u的左右儿子都算出来
            build(u << 1, l, mid);  // 先递归下左儿子 
            build(u << 1|1, mid + 1, r);  // 再递归下右儿子
            push_up(u);  // 然后再通过这个函数算出u结点 包含区间的值
        }
    }
    int query(int u, int l, int r)  // 查询的过程是从根结点开始往下找对应的区间的 所以第一个参数可以说默认就是1了
    {
        
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;  // 如果当前的这个结点所表示的区间被 我们需要的区间
        // 完全包含 那么就直接返回这个区间的值
        
        // 反之就对没有完全包含的子区间 分割 知道 分到 子区间的某个子区间 被完全包含为止
        int mid = tr[u].l + tr[u].r >> 1; // 先计算下 当前这个区间 与[l, r]有没有交集 交集在那一部分
        int sum = 0;  // 区间[l, r]的和
        
        // 这两句话的理解要加上二叉树的那个图像 才好理解 本质就是不断缩小区间然后 知道 寻找到一个u的左右边界 被[l, r]
        // 完全包含
        if (mid >= l) sum += query(u << 1, l, r); // 看看当前的区间的中点与待查区间的左边有没有交集
        if (mid + 1 <= r) sum += query(u << 1 | 1, l, r); // 再看看这个u这个区间的中点与[l, r]的右边有没有交集
        
        return sum;
    }
    void modify(int u, int x, int v) // 第一个参数还是默认根结点， 后面就是 在x的基础上加上v
    {
        
        if (tr[u].l == tr[u].r) tr[u].sum += v;  // 找到根结点了
        else 
        {
        
            int mid = tr[u].l + tr[u].r >> 1;
            
            // 寻找一下x是在u结点区间的左半边还是右半边
            if (x <= mid) modify(u << 1, x, v); // 在左半边的情况
            else modify(u << 1 | 1, x , v);  // 在右半边的情况
            
            // 更新完之后在往上把与被修改的叶子结点 有关联的父结点的值都修改一遍
            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]区间的线段树
        while (m --) 
        {
        
            int k, a, b;
            scanf ("%d%d%d", &k, &a, &b);
            if (!k) printf("%d\n", query(1, a, b));
            else modify(1, a, b);
        }
        return 0;
    }

**Java**

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main {
        
        static int N = 100010;
        static int n;
        static int m;
        static int[] w = new int[N];
        static Node[] tr = new Node[N * 4];
        //用子节点信息来更新当前节点信息（把信息往上传递）
        public static void pushUp(int u)
        {
        
            tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
        }
        //在一段区间上初始化线段树，其中u表示根结点，l表示左边界，r表示右边界
        public static void build(int u,int l,int r)
        {
        
            if(l == r) tr[u] = new Node(l,r,w[r]);
            else
            {
        
                tr[u] = new Node(l,r,0);
                int mid = l + r >> 1;
                build(u << 1,l,mid);
                build(u << 1 | 1,mid + 1,r);
                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].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;
        }
        //修改操作，在u结点中，x位置加上v
        public static 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);
            }
        }
        public static void main(String[] args) throws IOException {
        
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String[] s1 = reader.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            String[] s2 = reader.readLine().split(" ");
            for(int i = 1;i <= n;i++) w[i] = Integer.parseInt(s2[i - 1]);
            //搭建线段树
            build(1,1,n);
    
            while(m -- > 0)
            {
        
                String[] s3 = reader.readLine().split(" ");
                int k = Integer.parseInt(s3[0]);
                int x = Integer.parseInt(s3[1]);
                int y = Integer.parseInt(s3[2]);
                //k = 0 是询问[x,y]的区间和，k = 1是在x位置添加y元素
                if(k == 0) System.out.println(query(1,x,y));
                else modify(1,x,y);
            }
        }
    }
    //段结点
    class Node
    {
        
        public int l;//左边界
        public int r;//右边界
        public int sum;//当前块的总和
    
        public Node(int l,int r,int sum)
        {
        
            this.l = l;
            this.r = r;
            this.sum = sum;
        }
    }

[f5e4074b85844d62a742e0a0ccb3bd70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/28aee808adc140f78a475a35274c0cff.png