精华内容
下载资源
问答
  • 2019-10-22 11:46:04

    https://www.luogu.org/problem/P3374
    开始,我的单点修改只改变的线段树上的一个结点的值,实际上,要改变一连串的值才可以。

    更多相关内容
  • 单点修改,区间查询 例题】 【hdu 1166 敌兵布阵】 【hdu 1754I Hate It 】 【区间修改,区间查询 例题】 【hdu 1698Just a Hook】 【单点修改,区间查询 例题】 1.单点修改、区间查询 - hdu 1166 敌兵布阵...

    目录

    【单点修改,区间查询 例题】

    【hdu 1166 敌兵布阵】

    【hdu 1754 I Hate It 】

    【区间修改,区间查询 例题】

    【hdu 1698 Just a Hook】


    【单点修改,区间查询 例题】

    1.单点修改、区间查询 - hdu 1166 敌兵布阵

    2.单点修改、区间查询最值 - hdu 1754 I Hate It

    【hdu 1166 敌兵布阵】

    敌兵布阵

    【代码】

    const int maxn=50000;
    int n,a[maxn+10];
    int sum[4*maxn+10];
    void build(int k,int l,int r)
    {
        if(l==r)
        {
            sum[k]=a[l];
            return;
        }
        int mid=l+r>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        sum[k]=sum[k<<1]+sum[k<<1|1];
    }
    void change(int k,int l,int r,int x,int v)
    {
        if(r<x||l>x) return;
        if(l==r&&l==x)
        {
            sum[k]+=v;
            return;
        }
        int mid=l+r>>1;
        change(k<<1,l,mid,x,v);
        change(k<<1|1,mid+1,r,x,v);
        sum[k]=sum[k<<1]+sum[k<<1|1];
    }
    int query(int k,int l,int r,int x,int y)
    {
        if(y<l||x>r) return 0;
        if(l>=x&&r<=y) return sum[k];
        int mid=l+r>>1;
        int res;
        res=query(k<<1,l,mid,x,y);
        res+=query(k<<1|1,mid+1,r,x,y);
        return res;
    }
    int main()
    {
        int t; scanf("%d",&t);
        for(int _=1;_<=t;_++)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            build(1,1,n);
            printf("Case %d:\n",_);
            char s[10];
            while(~scanf("%s",s))
            {
                int x,y;
                if(s[0]=='E') break;
                scanf("%d%d",&x,&y);
                if(s[0]=='A') change(1,1,n,x,y);
                else if(s[0]=='S') change(1,1,n,x,-y);
                else printf("%d\n",query(1,1,n,x,y));
            }
        }
        return 0;
    }
    

    【hdu 1754 I Hate It 】

    I Hate It

    线段树单点修改区间查询最值模板题。

    【代码】

    const int maxn=200000;
    int n,a[maxn+10];
    int ma[4*maxn+10];
    void build(int k,int l,int r)
    {
        if(l==r)
        {
            ma[k]=a[l];
            return;
        }
        int mid=l+r>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        ma[k]=max(ma[k<<1],ma[k<<1|1]);
    }
    void change(int k,int l,int r,int x,int v)
    {
        if(r<x||l>x) return;
        if(l==r&&l==x)
        {
            ma[k]=v;
            return;
        }
        int mid=l+r>>1;
        change(k<<1,l,mid,x,v);
        change(k<<1|1,mid+1,r,x,v);
        ma[k]=max(ma[k<<1],ma[k<<1|1]);
    }
    int query(int k,int l,int r,int x,int y)
    {
        if(y<l||x>r) return 0;
        if(l>=x&&r<=y) return ma[k];
        int mid=l+r>>1;
        int res;
        res=max(query(k<<1,l,mid,x,y),query(k<<1|1,mid+1,r,x,y));
        return res;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            build(1,1,n);
            while(m--)
            {
                char c; int x,y;
                scanf(" %c%d%d",&c,&x,&y);
                if(c=='U') change(1,1,n,x,y);
                else printf("%d\n",query(1,1,n,x,y));
            }
        }
        return 0;
    }
    

    【区间修改,区间查询 例题】

    【hdu 1698 Just a Hook】

    Just a Hook

    区间修改、区间查询区间和

    【标记下传】

    const int maxn=100000;
    int n,a[maxn+10];
    int add[4*maxn+10],sum[4*maxn+10];
    void build(int k,int l,int r)
    {
        if(l==r)
        {
            sum[k]=1;
            return;
        }
        int mid=l+r>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        sum[k]=sum[k<<1]+sum[k<<1|1];
    }
    void Add(int k,int l,int r,int v)        //把区间[l,r]所有数变成v
    {
        add[k]=v;          //打标记
        sum[k]=(r-l+1)*v;  //维护区间和
        return;
    }
    void pushdown(int k,int l,int r,int mid) //标记下传
    {
        if(add[k]==0) return;         //没有标记则不用考虑
        Add(k<<1,l,mid,add[k]);       //下传到左子树
        Add(k<<1|1,mid+1,r,add[k]);   //下传到右子树
        add[k]=0;                     //清零
    }
    void modify(int k,int l,int r,int x,int y,int v)  //给定区间[x,y]所有数变成v
    {
        if(l>=x&&r<=y) return Add(k,l,r,v);
        int mid=l+r>>1;
        pushdown(k,l,r,mid);          //到达每一个结点都要下传标记
        if(x<=mid) modify(k<<1,l,mid,x,y,v);
        if(mid<y) modify(k<<1|1,mid+1,r,x,y,v);
        sum[k]=sum[k<<1]+sum[k<<1|1];     //下传后更新sum
    }
    int query(int k,int l,int r,int x,int y)          //询问区间[x,y]的和
    {
        if(l>=x&&r<=y) return sum[k];
        int mid=l+r>>1,res=0;
        pushdown(k,l,r,mid);       //下传标记
        if(x<=mid) res+=query(k<<1,l,mid,x,y);
        if(mid<y) res+=query(k<<1|1,mid+1,r,x,y);
        return res;
    }
    
    int main()
    {
        int t,n,q; scanf("%d",&t);
        for(int k=1;k<=t;k++)
        {
            mem(add,0);
            scanf("%d%d",&n,&q);
            build(1,1,n);
            while(q--)
            {
                int x,y,v;
                scanf("%d%d%d",&x,&y,&v);
                modify(1,1,n,x,y,v);
            }
            printf("Case %d: The total value of the hook is %d.\n",k,query(1,1,n,1,n));
        }
        return 0;
    }
    

    【~~】

    展开全文
  • 简单的线段树单点查询, 单点修改 AC代码: #include #include #include #include #include #include #include using namespace std; const int maxn = 50005; int n, people[maxn], sum[maxn <<

    敌兵布阵

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
    Total Submission(s): 80802    Accepted Submission(s): 34133


    Problem Description
    C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
    中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.
     

    Input
    第一行一个整数T,表示有T组数据。
    每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
    接下来每行有一条命令,命令有4种形式:
    (1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
    (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
    (3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
    (4)End 表示结束,这条命令在每组数据最后出现;
    每组数据最多有40000条命令
     

    Output
    对第i组数据,首先输出“Case i:”和回车,
    对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
     

    Sample Input
      
    1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End
     

    Sample Output
      
    Case 1: 6 33 59
     

    Author
    Windbreaker
     

    Recommend
    Eddy


    简单的线段树单点修改,单点查询

    AC代码:

    #include<cstdio>
    #include<cstring>   
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<cmath>
    #include<iomanip>
    
    using namespace std;
    const int maxn = 50005;
    int n, people[maxn], sum[maxn << 2];
    
    void pushup(int rt) {
    	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    
    
    void build(int l, int r, int rt) {
    	if(l == r) {
    		sum[rt] = people[l];
    		return;
    	}
    	int m = (l + r) >> 1;
    	build(l, m, rt << 1);
    	build(m + 1, r, rt << 1 | 1);
    	pushup(rt);
    }
    
    //单点修改
    void update(int node, int data, int D, int l ,int r, int rt) {
    	if(l == r) {
    		if(D == 1) //D=1代表加 
    			sum[rt] += data;
    		else sum[rt] -= data;
    		return;
    	}
    	
    	int m = (r + l) >> 1;
    	if(node <= m)  update(node, data, D, l, m, rt << 1);
    	else  update(node, data, D, m + 1, r, rt << 1 | 1);
    	pushup(rt);
    }
    
    int query(int L, int R, int l, int r, int rt) {
    	if(l >= L && r <= R)
    		return sum[rt];
    	
    	int m = (l + r) >> 1;
    	int ans = 0;
    	if(L <= m)  ans += query(L, R, l, m, rt << 1);
    	if(R > m)  ans += query(L, R, m + 1, r, rt << 1 | 1);
    	return ans;
    }
    
    int main()
    {
    	int t, cnt = 0, i, a, b;
    	char que[6];
    	scanf("%d",&t);
    	while(t--) {
    		printf("Case %d:\n",++cnt);
    		scanf("%d",&n);
    		for(i=1; i<=n; ++i)
    			scanf("%d",&people[i]);
    		build(1, n, 1);
    		
    		while(scanf("%s",que)) {
    			if(!strcmp(que, "End"))
    				break;
    			scanf("%d %d",&a, &b);
    			if(!strcmp(que, "Query")) {
    				printf("%d\n",query(a, b, 1, n, 1));
    			}
    			else if(!strcmp(que,"Add")) {
    				update(a, b, 1, 1, n, 1);
    			}
    			else if(!strcmp(que,"Sub")) {
    				update(a, b, 0, 1, n, 1);
    			}
    		}
    	}
    	return 0;
    }



    展开全文
  • 1547:【 例 1】区间和 (信息...给定一数列,规定有两种操作,一是修改某个元素,二是求区间的连续和。 【输入】 输入数据第一行包含两个正整数n,m(n≤100000,m≤500000),以下是m行, 每行有三个正整数k,a,b(k=...

    1547:【 例 1】区间和 (信息学一本通网站)

    时间限制: 1000 ms         内存限制: 524288 KB
    提交数: 1175     通过数: 318 

    【题目描述】

    给定一数列,规定有两种操作,一是修改某个元素,二是求区间的连续和。

    【输入】

    输入数据第一行包含两个正整数n,m(n≤100000,m≤500000),以下是m行,

    每行有三个正整数k,a,b(k=0或1,a,b≤n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。

    【输出】

    对于每个询问输出对应的答案。

    【输入样例】

    10 20
    0 1 10
    1 1 4
    0 6 6
    1 4 10
    1 8 9
    1 4 9
    0 10 2
    1 1 8
    0 2 10
    1 3 9
    0 7 8
    0 3 10
    0 1 1
    1 3 8
    1 6 9
    0 5 5
    1 1 8
    0 4 2
    1 2 8
    0 1 1

    【输出样例】

    10
    6
    0
    6
    16
    6
    24
    14
    50
    41

    模板题

    #include<bits/stdc++.h>
    #define N 100000+5
    #define LL long long
    using namespace std;
    int n,m,v;
    LL a[N],t[4*N];//线段树必须为4*N 空间
    
    //传入的参数为 k当前需要建立的结点;l当前需要建立的左端点;r当前需要建立的右端点
    void build(int k,int L,int R) {
    	if (L==R) t[k]=a[L];//当左端点等于右端点即建立叶子结点时,直接给数组信息赋值
    	else {
    		int mid = (L+R)/2;
    		build(k*2,L,mid);
    		build(k*2+1,mid+1,R);
    		t[k] = t[k*2] + t[k*2+1];//递归返回时用儿子结点更新父节点,此处可进行更新最大值、最小值、区间和等操作
    	}
    }
    
    //单点修改:
    //k、l、r为当前更新到的结点、左右端点,
    //x为需要修改的叶子结点左端点
    //y为需要修改成的值;
    void update(int k,int l,int r,int x,int y) {
    	if(l==r) {
    		a[x]+=y;
    		t[k]+=y;
    		return;
    	}
    	int mid=(l+r)/2;
    	if (x>=l&&x<=mid) update(k*2,l,mid,x,y);
    	else update(k*2+1,mid+1,r,x,y);
    	t[k]=t[k*2]+t[k*2+1];
    }
    
    LL query(int k,int l,int r,int x,int y) { //x、y为需要查询的区间左右端点
    	//若当前结点和需要查找的区间不相交,则返回一个对于区间查询无关的值
    	//(如求和时返回0,求最大值时返回-1等)
    	if (x>r||y<l) return 0;
    	//若当前结点的区间被需要查询的区间覆盖,则返回当前结点的信息
    	if (x<=l&&y>=r) return t[k];
    	int mid=(l+r)/2;
    	//p1为查询左儿子结点得到的信息,p2为查询右儿子结点得到的信息
    	LL p1=query(k*2,l,mid,x,y);
    	LL p2=query(k*2+1,mid+1,r,x,y);
    	return p1+p2;综合两个儿子结点的信息并返回return p1+p2
    
    }
    
    int main() {
    	scanf("%d%d",&n,&m);
    	//build(1,1,n);
    	while(m--) {
    		int k,a,b;
    		scanf("%d%d%d",&k,&a,&b);
    		if (k==0) {
    			update(1,1,n,a,b);
    		} else {
    			LL ans=query(1,1,n,a,b);
    			printf("%lld\n",ans);
    		}
    	}
    
    	return 0;
    }

     

    展开全文
  • 线段树 单点修改、区间查询模板
  • 题目链接:单点修改,区间查询 build:基于后序遍历和区间二分的思想,递归建树 change:1、r<x||l>x,当前区间与要修改的点无交集,直接return掉 2、l==r&&l==x,这个点为要修改的点,把对应位置...
  • //线段树 单点修改 区间查询 #include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 7; int n, m, a[N]; struct node { int l, r, sum; //一条线段 边界 值 }; struct ...
  • 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,... 在这片文章中,我先讲一下最基本的建树,单点修改,单点/区间查询 线段树是一种用空间换时间的算法开建树的数组时切记 一定要开4倍的...
  • 题目来源: ... 借鉴大牛李的线段树模板 const int Max_N=50100; ...int sum[Max_N2] ; // 线段树中每个需要维护的区间和 int x[Max_N]; // 输入数组 //从下向上更新值 void push_up(int root){ sum[r
  • 单点修改+区间修改和查询 例题+代码 目录 【线段树】 【引入】 【概述】 【单点修改和查询】 【建树】 【单点修改】 【区间查询最小值】 【区间查询区间和】 【区间修改和查询】 【延迟标记】 【标记下...
  • HDU1854 - 线段树 单点修改区间最大值 HDU1854 - 线段树 单点修改区间最大值 题目链接: I Hate It 题目大意 很多学校流行一种比较的习惯。老师们很喜欢询问,从...
  • 如果有神犇会区间修改的非递归版本,求教啊线段树单点修改,区间查询最小值 可以看见我这代码里面全是for循环 zkw 大法好正常线段树是一颗近似的满二叉树,因为n不是2的k次方 就这样凑成了一个满二叉树M可以...
  • //单点修改,区间查询 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; const int maxn = 50005; int sum[maxn]; void push_up(int root) { sum[root] = ...
  • int main(){ //线段树单点修改模板题 string s; int t,n,i,j,u,v,cas; scanf("%d",&t); for(cas=1;cas;cas++){ scanf("%d",&n); build(1,n,1); printf("Case %d:\n",cas); while(cin>>s&&s!="End"){ scanf...
  • 线段树介绍: 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子...
  • 思路:用线段树的每一层来维护上述的每一次操作。标记叶子节点为XOR操作,根节点的标记与儿子节点的标记相反,表示不同的两种操作。修改维护的时候,直接对两个子树维护的值进行位运算即可。最后输出线段树根节点...
  • 它功能强大,支持区间求和,区间最大值,区间修改,单点修改等操作。 线段树的思想和分治思想很相像。 线段树的每一个节点都储存着一段区间[L…R]的信息,其中叶子节点L=R。它的大致思想是:将一段大区间平均地...
  • //C a b 将a值改为b #include<bits/stdc++.h> using namespace std; #pragma warning(disable:4996) #define maxn 100005 #define ll long long ll chushi[maxn], sum[maxn * 4];//记...
  • 题目 描述 Description 给定一个包含n个数的序列,初值全为0,现对这个序列有两种操作: 操作1:把 给定 第k1 个数改为k2; 操作2:查询 从第k1个数到第k2个数得最大值。(k1<=k2<=n) 所有的数都 <...
  • 线段树(Segmen Tree)是一种基于分治思想的二叉树结构,用于在区间上进行信息统计。与按照二进制位(2的次幂)进行区间划分的树状数组相比,线段树是一种更加通用的结构。 1、线段树的每个节点都代表一个区间。 2、...
  • 很久以前就想做,但不知道如何转换,跟另外一题差不多的意思,主要是进行单点修改的应该怎么写要知道据说树状数组更快,然而并不是是很懂树状数组的原理,只会模版,就直接用线段树做了。 代码: #include ...
  • 线段树(单点修改)

    2021-05-27 17:58:27
    线段树功能 update(arr, i, val) 把arr[i]中的数字改成val query(arr,L,R)计算数组arr中,从下标L到下标R之间的所有数字的和 朴素做法的update和query的复杂度只能做到一个为O(1)另一个为O(n) 通过线段树可以使update...
  • 由于命令长度最大才30,...把每一个shift操作当成N个单点修改即可。 对命令字符串解析,使用: for(int j=0;j  if(isdigit(s[j])){  sscanf(&s[j],"%d",&pos[p++]);  }  while(isdigit(s[j])){  j++;  
  • 简单的单点修改,求区间最值 #include #define max_N 800000 using namespace std; int ans; //求和 int big; //求最大值 struct seg{ int l,r,v,maxn; }tree[max_N]; void build(int l,int r,int k) { tree[k].

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,458
精华内容 6,583
关键字:

线段树单点修改