本文共 4364 字，大约阅读时间需要 14 分钟。

线段树（c++）

需求：

必须：二分法，树的基础

建议先看看这个：

https://blog.csdn.net/zearot/article/details/52280189

线段树，类模板题

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int t=100009;struct node{
   	int v,l,r,mid;}tree[t<<2]; void pushdown(int rt){
   	tree[rt<<1].v=tree[rt<<1|1].v=tree[rt].v;	tree[rt].v=-1;}void build(int l,int r,int rt){
   	tree[rt].l=l;	tree[rt].r=r;	tree[rt].v=1;	tree[rt].mid=(l+r)>>1;	if(l==r)	{
   		return;	}	build(l,tree[rt].mid,rt<<1);	build(tree[rt].mid+1,r,rt<<1|1);}void add(int l,int r,int v,int rt){
   	if(tree[rt].l>=l&&tree[rt].r<=r)	{
   		tree[rt].v=v;		return;	}		if(tree[rt].v!=-1)	pushdown(rt);	if(r<=tree[rt].mid)	{
   		add(l,r,v,rt<<1);	}else if(l>tree[rt].mid){
   		add(l,r,v,rt<<1|1);	}else{
   		add(l,tree[rt].mid,v,rt<<1);		add(tree[rt].mid+1,r,v,rt<<1|1);	}}int find(int rt){
   	if(tree[rt].v!=-1)	return tree[rt].v*(tree[rt].r-tree[rt].l+1);	else	return find(rt<<1)+find(rt<<1|1);}int main() {
   	int N,n,m,i,j,k,v,c=0;	cin>>N;	while(N--)	{
   		scanf("%d %d",&n,&m);		build(1,n,1);		for(i=1;i<=m;i++)		{
   			scanf("%d%d%d",&j,&k,&v);			add(j,k,v,1);		}		printf("Case %d: The total value of the hook is %d.\n",++c,find(1));	}	return 0;}
       
      
     
    
   

拓展：

其中用到了lowbit()函数，相比其余方法的代码可以说是精简了不少，但要明白其中的原理，还需掌握补码，反码，移码等相关知识。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int c[50100];int lowbit(int t){ return t&(-t);}int getSum(int n){ int sum=0; while(n>0) { sum+=c[n]; n-=lowbit(n); } return sum;}void change(int i,int v,int n){ while(i<=n) { c[i]+=v; i+=lowbit(i); }}int main(){ int T; cin>>T; int num=1; while(T--) { memset(c,0,sizeof(c)); cout<<"Case "<
         
          <<":\n"; int N,a; cin>>N; for(int i=1;i<=N;i++) { scanf("%d",&a); change(i,a,N); } char cmd[10]; while(scanf("%s",cmd),cmd[0]!='E') { int p,q; if(cmd[0]=='A') { scanf("%d%d",&p,&q); change(p,q,N); }else if(cmd[0]=='S'){ scanf("%d%d",&p,&q); change(p,-q,N); }else{ scanf("%d%d",&p,&q); if(p!=1) printf("%d\n",getSum(q)-getSum(p-1)); else printf("%d\n",getSum(q)); } } } return 0;}
         
        
       
      
     
    
   

正常做法

#include 
   
    #include 
    
     using namespace std;const int maxn = 5e4 + 10;int ans;struct node {
       int left, right, sum;} tree[maxn * 4];void build(int left, int right, int rt) {
       tree[rt].left = left;    tree[rt].right = right;    if (left == right) {
           scanf("%d", &tree[rt].sum);        return;    }    int mid = (tree[rt].left + tree[rt].right) / 2;    build(left, mid, rt * 2);    build(mid + 1, right, rt * 2 + 1);    tree[rt].sum = tree[rt * 2].sum + tree[rt * 2 + 1].sum;}void update(int left, int right, int rt, int pos, int add) {
       if (left == right) {
           tree[rt].sum += add;        return;    }    int mid = (tree[rt].left + tree[rt].right) / 2;    if (pos <= mid) {
           update(left, mid, rt * 2, pos, add);    } else {
           update(mid + 1, right, rt * 2 + 1, pos, add);    }    tree[rt].sum = tree[rt * 2].sum + tree[rt * 2 + 1].sum;}void query(int left, int right, int rt, int L, int R) {
       if (L <= left && right <= R) {
           ans = ans + tree[rt].sum;        return;    }    int mid = (tree[rt].left + tree[rt].right) / 2;    if (R <= mid) {
           query(left, mid, rt * 2, L, R);    } else if (L > mid) {
           query(mid + 1, right, rt * 2 + 1, L, R);    } else {
           query(left, mid, rt * 2, L, R);        query(mid + 1, right, rt * 2 + 1, L, R);    }}int main() {
       int t, n, cnt, a, b;    char str[10];    cnt = 1;    cin >> t;    while (t--) {
           cin >> n;        build(1, n, 1);        printf("Case %d:\n", cnt++);        while (cin >> str) {
               if (str[0] == 'E') {
                   break;            }            cin >> a >> b;            if (str[0] == 'Q') {
                   ans = 0;                query(1, n, 1, a, b);                printf("%d\n", ans);            } else if (str[0] == 'A') {
                   update(1, n, 1, a, b);            } else if (str[0] == 'S') {
                   update(1, n, 1, a, -b);            }        }    }    return 0;}
    
   

最后

转载地址：https://blog.csdn.net/weixin_43820352/article/details/88969542 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！