树状数组
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], tr[N];
int lowbit(int x)
{
return x & -x;
}
//在x的位置上添加一个数k
void add(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}
//查询s[x]
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]);
//初始化树状数组:把每个为之视为0,将a[i]加进去就行
for(int i = 1; i <= n; i++) add(i, a[i]);
int k, x, y;
while(m --)
{
scanf("%d%d%d", &k, &x, &y);
if(k == 0) printf("%d\n", query(y) - query(x - 1));
else add(x, y);
}
return 0;
}
线段树
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int w[N]; //记录权重
struct Node {
int l, r; //左右区间
int sum; //总和
}tr[N * 4]; //最高达到4N的查找范围
//用两个儿子节点计算当前节点的信息
void push_up(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
//初始化线段树
/*
* u:当前节点编号
* l:左边界
* r:右边界
*/
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, w[r]}; //如果当前已经是叶子节点,就直接赋值,即区间长度=1
else //当前 区间长度>1 需要将区间分为左右两个区间
{
tr[u] = {l, r}; //记录左右边界初始值
int mid = l + r >> 1; //设置边界值:下取整 l + r
build(u << 1, l, mid); //递归左儿子,做相同的构造
build(u << 1 | 1, mid + 1, r); //递归右儿子
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); //查看当前区间的中点与左区间l是否有交集
if(r > mid) sum += query(u << 1 | 1, l, r); //查看当前区间的中点与右区间r是否有交集
return sum;
}
//修改
/*
* u:当前节点编号
* x:要修改的位置
* v:要修改的值
*/
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); //如果在右半边,就递归去右儿子做修改
//更新完子节点之后就需要对祖先节点进行更新
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 初始区间:1~n
while(m --)
{
int k, a, b;
scanf("%d%d%d", &k, &a, &b);
if(k == 0) printf("%d\n", query(1, a, b)); //求和
else modify(1, a, b); //修改
}
return 0;
}