精华内容
下载资源
问答
  • 一直用 线段 求区间最大值,想换种思路,用树状数组试试,肯定是可以的。 首先要对 树状数组的每个 i所管理的区间有一定的理解。详见上篇博客:树状数组(BIT) 如图, A数组表示的时输入的数组, C 是树状...

       一直用 线段树 求区间最大值,想换种思路,用树状数组试试,肯定是可以的。

     

    首先要对 树状数组的每个 所管理的区间有一定的理解。详见上篇博客: 树状数组(BIT)

     

    如图, A数组表示的时输入的数组, C 是树状数组,

    树状数组 C[i] 所包含的区间时 [ i - lowbit(i) + 1, i], 其中区间的个数是 lowbit(i) 个, C[i] 一定包含A[i]

    之后就可以像 线段树一样进行区间更新和查询操作了.需要更新(查询)子区间就更新(查询)子区间,需要更新(查询)父结点就更新(查询)父结点,

    HDU1754 为例, 代码如下:

    //Author LJH
    //www.cnblogs.com/tenlee
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cctype>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <map>
    #define clc(a, b) memset(a, b, sizeof(a))
    #define LL long long
    using namespace std;
    
    const int inf = 0x3f;
    const int INF = 0x3f3f3f3f;
    const int maxn = 1e6+5;
    
    int a[maxn], c[maxn];
    int n, m;
    
    int lowbit(int x)
    {
        return x & (-x);
    }
    
    void Build(int id, int val)
    {
        a[id] = val;
        while(id <= n)
        {
            c[id] = max(c[id], val);
            id += lowbit(id);
        }
    }
    
    void Update(int id, int val)
    {
        a[id] = val;
        int i = id, j, k;
        while(i <= n)
        {
            c[i] = a[i];
            if(lowbit(i) > 1) //c[i] 包含区间内元素个数
            {
                k = i - lowbit(i) + 1; // c[i] 所包含区间的左端点
                j = i - 1;
                while(j >= k) //向下查找
                {
                    c[i] = max(c[i], c[j]);
                    j -= lowbit(j);
                }
            } 
            i += lowbit(i); //向上更新
        }
    }
    
    int Query(int ll, int rr)
    {
        int ans = a[rr];
        while(true)
        {
            ans = max(ans, a[rr]);
            if(ll == rr) break;
    
            rr--; //一定要先减
            while(rr-ll >= lowbit(rr)) //向下查询子区间
            {
                ans = max(ans, c[rr]);
                rr -= lowbit(rr);
            }
        }
        return ans;
    }
    
    int main()
    {
        int x, y;
        char op;
        while(~scanf("%d %d",&n, &m))
        {
            clc(c, 0);
            for(int i = 1; i <= n; i++)
            {
                scanf("%d", &a[i]);
                Build(i, a[i]);
            }
            while(m--)
            {
                scanf(" %c %d %d", &op, &x, &y);
                if(op == 'Q')
                {
                    printf("%d\n", Query(x, y));
                }
                else
                {
                    Update(x, y);
                }
            }
        }
        return 0;
    }
    

     

     原文链接: http://sbp810050504.blog.51cto.com/2799422/1051811

    转载于:https://www.cnblogs.com/tenlee/p/4779529.html

    展开全文
  • 思路见树状数组求区间最大值 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N = 300000+5; in...

    //注意题意:文件结束......

    //数组清零应放在循环里

    思路见树状数组求区间最大值

     

    
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    
    using namespace std;
    const int N = 300000+5;
    
    int a[N], c[N];//原数组和存放最大值 
    int n, m;
    
    int lowbit(int x)
    {
    	return x&(-x);
    }
    
    void Update(int x)
    {
    	int l;
    	
    	while(x <= n){
    		
    		c[x] = a[x];
    		
    		l = lowbit(x);
    		
    		for(int i=1; i<l; i <<= 1){
    			c[x] = max(c[x], c[x-i]);
    		}
    		
    		x += lowbit(x);
    	}
    	
    }
    
    void Update(int i, int val)
    
    {
    
    	while (i <= n)
    
    	{
    
    		c[i] = max(c[i], val);
    
    		i += lowbit(i);
    
    	}
    
    }
    
    
    int Query(int x, int y)
    {
    
    	int ans = 0;
    
    	while (y >= x){
    		
    		if(y-lowbit(y) < x){
    		ans = max(a[y], ans);
    		y --;
    	}
    		
    		while(y-lowbit(y) >= x){
    			ans = max(c[y], ans);
    			y -= lowbit(y);
    
    		}
    	}
    
    
    	return ans;
    
    }
    
    int main()
    {
    
    	
    	while(~scanf("%d%d", &n, &m)){	
    		memset(c, 0, sizeof(c));
    	
    	for(int i=1; i<=n; i++){
    		scanf("%d", a+i);
    //		Update(i);
    		Update(i, a[i]);
    	}
    	
    	getchar();
    //	for(int i=0; i<m; i++)//不知道为什么 i每次在数据处理了以后都会变为0.... 
    	while(m--){
    		char c[1];
    		int x, y;
    		
    		scanf("%s", c);
    		//getchar();
    	//	cout << c << endl ;
    	//	if(strcmp(c.c_str(), "Q") == 0){
    		if(!strcmp(c, "Q")){
    			scanf("%d%d",&x,&y);
    
    			printf("%d\n", Query(x, y));
    		}
    		else {
    			scanf("%d%d",&x,&y);
    
    			a[x] = y;
    			//Update(x);
    			Update(x, a[x]);
    		}
    	
    	}
    }
    	
    	
    	return 0;
     } 

     

    展开全文
  • 树状数组的实现原理就不讲了,这里要特别说明的是,lowbit(x) 不仅可以表示区间分块对应存储前缀的位置,同时还能够表示一个区间的长度,这个长度在求区间最大值的时候起到比较重要的左右,也是我之前没想到的部分...

    以前一直把树状数组当作求前缀的工具,但事实上,树状数组是一种分块的方式,因为分块的方式比较独特,所以在求前缀的过程中非常方便;

    树状数组的实现原理就不讲了,这里要特别说明的是,lowbit(x) 不仅可以表示区间分块对应存储前缀的位置,同时还能够表示一个区间的长度,这个长度在求区间最大值的时候起到比较重要的左右,也是我之前没想到的部分;

    文字说明:

    求区间最大值 和 求区间和有很大的不同,因为树状数组求前缀和十分方便,所以通过 sum (R) - sum (L-1) 就能得到一个区间的和;那么区间最大值怎么求?

    假设要求  L 到 R 的区间最大值,我们分块仍然是根据lowbit(x) 的方式分,对应分块的最大值也很容易想到,就是求前缀和中累加的部分改成 max () 就行了;

    查询: 如果我们根据lowbit 的规则从右向左求区间的最大值,所求的结果是 1 到 R 这个区间的最大值,显然答案可能是不正确的; 我们如何避开  1 到 L-1 这个区间?

    我们根据lowbit的规则,从右向左遍历区间块,如果是区间是我们要考虑的范围内就取这个最大值,如果发现当前的区间超出我们要考虑的范围就只取当前区间最末尾的值,然后lowbit - 1,然后继续从右向左遍历,直到所有区间取完为止。

    根据上图的步骤,下标为12的这个位置是 9 到 12的最大值,我们能通过lowbit知道当前区间的长度是多少,由此能知道当前区间是不是在我们要考虑的范围内;当遇到下标为8,区间长度大于当前我们要考虑的长度时,我们就只取最末尾的值,也就是对应数组a[8],lowbit - 1 到下标为7这个位置后继续从右向左判断,直到结束。 从图中可以很容易发现,以这种方式遍历,能把所有我们需要考虑的部分都遍历了一遍。

    下面这题是求区间最大值的模板题:HDU-1754 

    #include <iostream>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long ll;
    const int Maxn = 2e5+10;
    
    int a[Maxn], h[Maxn], n;  // a[] 数列的值,h[] 区间最大值
    
    void add (int x, int val) {
    	while (x <= n) {
    		h[x] = max (h[x], val); 
    		x += x&(-x);
    	}
    }
    
    int query (int L, int R) {
    	int ret = 0, len = R-L+1;
    	while (len && R) {  // len 是当前还需要判断的范围长度,R是对应区间最大值的下标
    		if (len < (R&(-R))) {
    			ret = max (ret, a[R]);
    			R--; len--;
    		} else {
    			ret = max (ret, h[R]);
    			len -= (R&(-R)); // 不断的缩短要判断的区间长度
    			R -= (R&(-R)); 
    		}
    	}
    	return ret;
    }
    
    int main (void)
    {
    	int m;
    	while (scanf ("%d%d", &n, &m) != EOF) {
    		memset (h, 0, sizeof (h));
    		for (int i = 1; i <= n; ++i) {
    			scanf ("%d", &a[i]);
    			add (i, a[i]);
    		}
    		char op[2], b[10]; int x, y;
    		while (m--) {
    			scanf ("%s%d%d", op, &x, &y);
    			gets (b);
    			if (!strcmp (op, "U")) {
    				a[x] = y; add (x, y);				
    			} else {
    				printf ("%d\n", query (x, y));
    			}
    		}
    		
    	}
    	return 0;
     } 

     

    展开全文
  • 设原数序列为a[i],最大值为h[i](树状数组)。 1。单点更新: 直接更新a[i],然后再更新h[i]。若h[i]的值有可能改变的,则表示区间一定包含i结点。那么就两层lowbit更新所有可能的h。 单点更新时间复杂度O(logn*...

    如题。

    当遇到单点更新时,树状数组往往比线段树更实用。

    算法:

    设原数序列为a[i],最大值为h[i](树状数组)。

    1。单点更新:

    直接更新a[i],然后再更新h[i]。若h[i]的值有可能改变的,则表示区间一定包含i结点。那么就两层lowbit更新所有可能的h。

    单点更新时间复杂度O(logn*logn)

     1 void update(int x)
     2 {
     3     while(x<=n)
     4     {
     5         h[x]=a[x];
     6         for(int i=1;i<lowbit(x);i<<=1)
     7         h[x]=max(h[x],h[x-i]);
     8         x+=lowbit(x);
     9     }
    10     return ;
    11 }

     

    2。区间查询最大值:

    设要查询的区间为[L,R],那么就从h[R]开始找,要找[L,R]内的所有区间。所以依然是两层lowbit,然后R向前跳直到跳到L前面。

    区间查询最大值时间复杂度O(logn*logn)

     1 void findans(int begin,int end)
     2 {
     3     int ans=0;
     4     while(end>=begin)
     5     {
     6         ans=max(ans,h[end]);
     7         end--;
     8         for(;end-lowbit(end)>=begin;end-=lowbit(end))
     9         ans=max(ans,h[end]);
    10     }
    11     
    12     printf("%d\n",ans);
    13     return ;
    14 }

     

    相关试题:hdu1754(单点修改,区间求最大值)

     1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<cmath>
     5 using namespace std;
     6 const int maxn=300005;
     7 int h[maxn],a[maxn];
     8 int n,m;
     9 int lowbit(int x)
    10 {
    11     return x&(-x);
    12 }
    13 void update(int x)
    14 {
    15     while(x<=n)
    16     {
    17         h[x]=a[x];
    18         for(int i=1;i<lowbit(x);i<<=1)
    19         h[x]=max(h[x],h[x-i]);
    20         x+=lowbit(x);
    21     }
    22     return ;
    23 }
    24 void findans(int begin,int end)
    25 {
    26     int ans=0;
    27     while(end>=begin)
    28     {
    29         ans=max(ans,a[end]);
    30         end--;
    31         for(;end-lowbit(end)>=begin;end-=lowbit(end))
    32         ans=max(ans,h[end]);
    33     }
    34     
    35     printf("%d\n",ans);
    36     return ;
    37 }
    38 int main()
    39 {
    40     //freopen("in.txt","r",stdin);
    41     //freopen("out.txt","w",stdout);
    42     while(scanf("%d%d",&n,&m)==2)
    43     {
    44         memset(h,0,sizeof(h));
    45         for(int i=1;i<=n;i++)
    46         {
    47             scanf("%d",&a[i]);
    48             update(i);
    49         }
    50         for(int i=1;i<=m;i++)
    51         {
    52             char c=getchar();
    53             while(c!='Q'&&c!='U')c=getchar();
    54             if(c=='U')//update
    55             {
    56                 int y,z;
    57                 scanf("%d%d",&y,&z);
    58                 a[y]=z;
    59                 update(y);
    60                 continue;    
    61             }
    62             if(c=='Q')//findans
    63             {
    64                 int y,z;
    65                 scanf("%d%d",&y,&z);
    66                 findans(y,z);
    67                 continue;
    68             }
    69         }
    70     }
    71     
    72     return 0;
    73 } 

     

    转载于:https://www.cnblogs.com/937337156Zhang/p/6072330.html

    展开全文
  • 树状数组求区间最大值(转载)

    千次阅读 2019-01-27 16:39:47
    2、在求区间最值的算法中,h[x]储存的是[x,x-lowbit(x)+1]中每个数的最大值求区间最值的算法中还有一个a[i]数组,表示第i个数是多少,也就是原数组。 [单点修改后的更新] 1、在维护区间和的算法中,是这样维护...
  • 树状数组求区间最值 很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求,写一个程序,模拟老师...
  • 树状数组(Binary Index Tree)利用二进制的一些性质巧妙的划分区间,是一种编程,时间和空间上都十分理想的求区间和的算法,同样我们可以利用树状数组优美的区间划分方法来一个序列的最值 约定以 num[] 表示原...
  • 点击打开链接
  • //维护区间最大值的算法,时间复杂度为O(n*logn) //即当要更新一个数时,把h[]清零,然后用a[] //数组去更新b[] void update1(int i,int val){ while(i){ h[i]=max(h[i],val); i+=lowbit(i); } } //O(...
  • 树状数组维护区间最大值,这个只支持末尾插入修改,每一次维护和查询的时间复杂度都是O((logn)^2),但这是满打满算的时间复杂度。假设是要维护和查询区间的最大值(最小值将max改成min 就好了)这个算法和树状数组...
  • 莫队算法。。不过 TLE
  • 树状数组求区间最值

    2019-06-29 12:27:16
    一个数组的前缀和本来是O(n)的复杂度,用树状数组则为O(nlogn)。 但树状数组优点在于单点更新时复杂度为O(logn),而正常的为O(n),这也就使得树状数组能够进行大规模的更新。 虽然查询速度(O(logn))稍有些慢(相...
  • 给定: 两个长度为n的数列A 、B 一个有m个元素的集合K ...每次询问[l,r],输出区间内满足|Bi-Bj|∈K 的最大Ai+Aj数据约定: n,Q m 0[i] 1[i] 1[i] 保证B[i]互不相等 Input n Q m A1 A2 ….An B1 B2 ….Bn K1
  • 题目:n个区间[l,r],m个操作:给数b,删去包含点b^res的区间,记录每个区间i第几次操作时被删去,每次操作删去的区间数。 res是上次删除的区间编号的乘积%998244353,如果上次未删区间,即res为0。 ...
  • 树状数组求区间极值

    2016-11-08 08:35:57
    假设是要维护和查询区间最大值(最小值将max改成min 就好了)这个算法和树状数组维护和查询区间和的方法很相似:一、数组的含义1、在维护和查询区间和的算法中,h[x]中储存的是[x,x-lowbit(x)+1]中每个数的和,2...
  • [Tjoi2016&Heoi2016]序列 Time Limit:20 SecMemory Limit:128 MBSubmit:1006Solved:464[Submit][Status][Discuss] Description ...玩具上有一个数列,数列中某些项的 可能会变化,但同一个时...
  • 树状数组求区间最值

    千次阅读 2014-08-08 23:52:31
    注意bit数组存放的是一个区间的最值。更新最值的时候要传递更新。查找的时候也要注意。如果已经不是在一个区间段上了,应该和num[]比。
  • [size=large][color=red]原理:求和时c数组存的是相应区间的和,而在这c数组(mkx数组的是相应区间最大值[/color][/size] [code="C++"]#include using namespace std; const int N = 400000+...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,573
精华内容 5,829
关键字:

树状数组求区间最大值