动态求连续区间和
给定 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
算法思路
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; } }
