Loading... #### 题目 给定 **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 ``` #### 树状数组模板 ```c++ #include<bits/stdc++.h> using namespace std; const int N = 100010; int n, m; int arr[N], tr[N]; int lowbit(int i){ return i & -i; } void add(int index, int x){ for(int i = index; i <= n; i += lowbit(i)) tr[i] += x; return; } void change(int index, int x){ int c = x - arr[index]; for(int i = index; i <= n; i += lowbit(i)) tr[i] += c; return; } int query(int index){ int res = 0; for(int i = index; i; i -= lowbit(i)) res += tr[i]; return res; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) scanf("%d", &arr[i]); for(int i = 1; i <= n; i++) add(i, arr[i]); while(m--){ int tag, l, r; int res; scanf("%d %d %d", &tag, &l, &r); if(tag) add(l, r); else printf("%d\n", query(r) - query(l - 1)); } return 0; } ``` #### 线段树模板 ```c++ #include<bits/stdc++.h> using namespace std; const int N = 100010; int n, m; int num[N]; struct node{ int l, r; int sum; }sgt[N * 4]; // 需要开N * 4 // 更新当前节点 void pushup(int root){ sgt[root].sum = sgt[root << 1].sum + sgt[root << 1 | 1].sum; } // 初始化线段树 void build(int root, int l, int r){ if(l == r) sgt[root].sum = num[l]; else{ sgt[root] = {l, r}; int mid = l + r >> 1; build(root << 1, l, mid); build(root << 1 | 1, mid + 1, r); pushup(root); } return; } int query(int root, int l, int r){ if(sgt[root].l >= l && sgt[root].r <= r) return sgt[root].sum; int mid = sgt[root].l + sgt[root].r >> 1; int sum = 0; if(l <= mid) sum += query(root << 1, l, r); if(r > mid) sum += query(root << 1 | 1, l, r); return sum; } void modify(int root, int index, int c){ if(sgt[root].l == sgt[root].r) sgt[root].sum += c; else{ int mid = sgt[root].l + sgt[root].r >> 1; if(index <= mid) modify(root << 1, index, c); else modify(root << 1 | 1, index, c); pushup(root); } } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) scanf("%d", &num[i]); build(1, 1, n); int k, a, b; while(m--){ scanf("%d %d %d", &k, &a, &b); if(k) modify(1, a, b); else printf("%d\n", query(1, a, b)); } return 0; } ``` Last modification：January 1, 2023 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed