线段树基本操作:1.单点查询
2.动态求连续区间和
3.求某个区间的单点最大/小值
4.区间修改(需要lazy tag才能O(logn))
若不是动态则仍是前缀和更方便
包含建树、单点查询 以及动态求和的模板题update:3/30;
#include<iostream>//O(mlogn);
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
struct tree{
int l, r;
int sum;
}T[4 * N];
void pushin(int no)
{
T[no].sum = T[no << 1].sum + T[no << 1 | 1].sum;
}
void init(int no, int l, int r)//建立线段树
{
if(l == r)
{
T[no] = {l, r, a[l]};
return;
}
T[no] = {l, r};//存入当前节点的左右端点
int mid = l + r >> 1;
init(no << 1, l, mid);//递归左孩子
init(no << 1 | 1, mid + 1, r);
pushin(no);
}
void modify(int no, int x, int d)//单点修改 在第x数的位置上加d
{
if(T[no].l == T[no].r)
{
T[no].sum += d;//加上d
return;
}
int mid = T[no].l + T[no].r >> 1;
if(x <= mid)modify(no << 1, x, d);
else modify(no << 1 | 1, x, d);
pushin(no);//叶子节点修改完后得向上递归sum;
}
int add(int no, int l, int r)//事实上是以二分形式缩小范围 直到区间能够被查询区间覆盖
{
//覆盖区间 动态查询连续区间和
if(T[no].l >= l && T[no].r <= r)
return T[no].sum;
// if(l <= T[no].l && r >= T[no].r)return T[no].sum;
int mid = T[no].l + T[no].r >> 1;
int sum = 0;
if(mid >= l)sum += add(no << 1, l, r);
if(mid + 1 <= r)sum += add(no << 1 | 1, l, r);
return sum;
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)cin >> a[i];
init(1, 1, n);
while(m--)
{
char op[2];
int a, b;
scanf("%s", op);
scanf("%d%d", &a, &b);
if(op[0] == '1')
{
modify(1, a, b);
// cout << T[1].sum << endl;
}
else
{
int res = add(1, a, b);
cout << res << endl;
}
}
return 0;
}