POJ 2309 BST 树状数组基本操作

POJ 2309 BST 树状数组基本操作

Description

Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for there queries. 



<span>POJ 2309 BST 树状数组基本操作</span>

Input

In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 2
31 – 1).

Output

There are N lines in total, the i-th of which contains the answer for the i-th query.

Sample Input

2
8
10

Sample Output

1 15
9 11

本题就考了树状数组的最最基本操作,对于会树状数组的人来说是太水了。

附个精简得不得了的代码,时间效率是O(1)

#include <stdio.h>
int main()
{
	int T, x;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &x);
		printf("%d %d\n", x-(x&(-x))+1, x+(x&(-x))-1);
	}
	return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/119129.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 为什么说hashmap是线程不安全的_map线程不安全

    为什么说hashmap是线程不安全的_map线程不安全 hashMap线程不安全的原因及表现hashMap出现线程不安全的原因:HashMap的实现里没有锁的机制,因此它是线程不安全的。其实只要有锁的机制,可以通过锁实现线程安全,我们在读写HashMap对象的时候加锁,以保障这个对象的线程安全,但不代表HashMap本身是线程安全的,因为是外力(你自己加的锁)使然。为啥不在HashMap内部加锁让它变成线程安全?这…

  • AWVS基本用法_awvs网页版使用教程

    AWVS基本用法_awvs网页版使用教程什么是AWVSAcunetixWebVulnerabilityScanner(简称AWVS)是一款知名的网络漏洞扫描工具,它通过网络爬虫测试你的网站安全,检测流行安全漏洞,现已更新到10。(下面用的是AWVS9)

  • 京东金融大数据竞赛猪脸识别(8)- 识别方法之四

    京东金融大数据竞赛猪脸识别(8)- 识别方法之四除了softmax层构建的深度网络,Matlab还有一个简单的构建数据分类的函数,那就是patternnet,其用法类似。可以直接对图像特征数据处理,也可以对图像集处理。代码如下:%exam1.m用训练图像特征构建深度网络并计算测试图像得分clear;load(‘JDPig_mlhmslbp_spyr.mat’);m=numel(classe_name);n=length(y)…

  • jb和jl_32纳米和22纳米有什么区别

    jb和jl_32纳米和22纳米有什么区别一个用于无符号数,一个用于有符号数,即使是在intel的官方手册中,JBE:JUMPSHORTIFBELOWOREQUALJLE:jumpshortiflessorequalbelow有人译为低于,less有人译为小于,但对于中国人来说,这两个完全是一个意思,很容易弄混…

    2022年10月26日
  • Centos7安装MySQL详细步骤

    Centos7安装MySQL详细步骤Centos7安装MySQL详细步骤首先在虚拟机中安装一个Centos7(VM虚拟机安装Centos7)1.1MySQL安装1.1.1下载wget命令yum-yinstallwget1.1.2在线下载mysql安装包wgethttps://dev.mysql.com/get/mysql57-community-release-el7-8.noarch.rpm1.1.3安装MySQLrpm-ivhmysql57-community-release-el7-8.noar

  • 数字时钟校时功能_公务员考试考场有钟表吗

    数字时钟校时功能_公务员考试考场有钟表吗数字时钟系统—标准化考场自动校时同步时钟

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号