详细注释版
算法1 线段树
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define rep(a,b,c) for(int a = b; a <= c; a++)
#define endl '\n'
#define ioput ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
int n,m,w[N];
struct Node
{
int l,r,sum;
}tr[4 * N];
void pushup(int u) // 计算节点u的存储的值:儿子节点的和相加
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u,int l,int r) // 构建根节点为u,大小是从l到n的一个线段树
{
tr[u] = {l,r}; // 初始化根节点lr
if (l == r) tr[u] = {l,r,w[r]}; // 到达子节点,其值为本身
else // 未到达子节点
{
int mid = l + r >> 1;
build(u << 1, l, mid),build(u << 1 | 1, mid + 1, r); // 左右儿子递归
pushup(u); // 计算节点u的值
}
}
int query(int u,int left,int right) // 计算从left到right的区间和,第一个参数为根结点编号
{
if (tr[u].l >= left && tr[u].r <=right) return tr[u].sum; // 完全包含 返回节点存储的值
// 否则
int mid = tr[u].l + tr[u].r >> 1; // 节点u的区间中点
int sum = 0; // 初始化值
if (left <= mid) sum += query(u << 1, left, right); // 如果左边和节点u的区间有交集,左儿子递归
if (right >= mid + 1) sum += query(u << 1 | 1, left ,right); // 右边有交集,右儿子递归
return sum;
}
void modify(int u,int x,int y) // 在编号为x的位置 加上y
{
if (tr[u].l == tr[u].r) tr[u].sum += y; // 叶节点,找到了x,加上y即可
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, y); // 如果x的位置在左子树,递归左儿子
else modify(u << 1 | 1, x, y); // 递归右儿子
pushup(u); // 重新计算u节点的值
}
}
int main()
{
ioput;
cin >> n >> m;
rep(i, 1, n) cin >> w[i];
build(1,1,n);
while (m -- )
{
int k, a, b;
cin >> k >> a >> b;
if (k == 0) cout << query(1,a,b) << endl;
else modify(1,a,b);
}
return 0;
}
算法2 树状数组
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#define ioput ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N = 1e5 + 10;
int n,m,k,a,b,num[N],tr[N];
int lowbit (int x)
{
return x & -x;
}
void add (int x, int y) // 将第x位置的元素加上y
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] +=y;
}
int query (int x) // 计算并返回1到x的元素的和 左开右闭
{
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
ioput;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> num[i];
for (int i = 1; i <= n; i++) add(i,num[i]);
for (int i = 1; i <= m; i++)
{
cin >> k >> a >> b;
if (k == 1)
{
add(a,b);
}
if (k == 0)
cout << query(b) - query(a-1) << endl;
}
return 0;
}