- C++
线段树模板-都不许看
- 2025-3-19 21:10:31 @
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6;
const int MAX_N_T = 4*MAX_N;
int tree[MAX_N_T];
int nums[MAX_N];
void build(int node ,int l,int r ){
if(l == r){
tree[node] = nums[l];
return;
}else{
int mid = (l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
}
int query(int node , int l,int r,int ql,int qr ){
if(ql>r || qr<l)return 0;
if(ql<=l && qr>= r)return tree[node];
int mid = (l + r)>>1;
int left = query(node<<1,l,mid,ql,qr);
int right = query(node<<1|1,mid+1,r,ql,qr);
return left+right;
}
void update(int node ,int l,int r, int index , int value){
if(l == r){
tree[node] = value;
return;
}
int mid = (l + r)>>1;
if(index<=mid){
update(node<<1,l,mid,index,value);
}else{
update(node<<1|1,mid+1,r,index,value);
}
tree[node] = tree[node<<1] + tree[node<<1|1];
}
int main(){
int n;
cin>>n;
for(int i =1 ; i <= n ; i ++){
cin>>nums[i];
}
build(1,1,n);
update(1,1,n,2,100);//索引值为2的元素更新成100
cout<<query(1,1,n,1,4);//查询索引值1->4的元素
return 0;
}
0 条评论
目前还没有评论...