标签: segment-tree

我正在实现一个分段树,以便能够快速回答数组A中的以下查询:

• 查询i,j:范围(i,j)中所有元素的总和
• 更新i,j,k:将k添加到范围(i,j)中的所有元素

这是我的实现:

typedef long long intt;

const int max_num=100000,max_tree=4*max_num;
intt A[max_num],ST[max_tree];

void initialize(int node, int be, int en) {
  if(be==en) {
    ST[node]=ST[be];
  } else {
    initialize(2*node+1,be,(be+en)/2);
    initialize(2*node+2,(be+en)/2+1,en);

    ST[node]=ST[2*node+1]+ST[2*node+2];
  }
}

void upg(int node, int be, int en, int i, intt k) {
  if(be>i || en<i || be>en) return;
  if(be==en) {
    ST[node]+=k;
    return;
  }
  upg(2*node+1, be, (be+en)/2, i, k);
  upg(2*node+2, (be+en)/2+1, en, i, k);
  ST[node] = ST[2*node+1]+ST[2*node+2];
}

intt query(int node, int be, int en, int i, …

我们在2D平面上给出N(N <= 10 ⁶)个点并且给出整数D(N <= 10 ⁶),我们想要找到两个点p1,p2(p1右边的p2)使得它们之间的差异p1.y并且p2.y至少是D并且p2.x - p1.x被最小化.

x轴和y轴的范围为0..10 ⁶

这是USACO过去的比赛中的一个问题.

这是我尝试解决它:
MAXY = N个点中的最大y轴.
假设我们知道p1,那么我们很容易找到p2; 通过将其y轴在该范围内的所有点都设置p1.y+D为MAXY或在0到0的范围内,p1.y-D并获取具有最大x轴的点大于p.x.这将是p2的最佳选择.

但是由于我们不知道p1,我们将不得不尝试p1的所有点,因此找到p2的最佳选择应该有效地完成.

我使用了一个分段树.树中的每个节点都将按照x轴的排序顺序存储相应范围内的所有点.在查询时,如果一个节点落在查询范围内,那么我们在数组上进行二进制搜索,p1.x并返回大于它的最小元素.

对于p1的每个选择,我们使用范围0,p1.yD和p1.y + D,MAXY两次查询树,并且在返回的两个点中取最佳值.

树的构建可以在O(NlogN)时间内完成.每个查询都需要O(logN*logN)时间,我们进行N次查询,因此所用的总时间为(Nlogn*logn),可能不会在2秒的时间限制内运行.(10 ⁶*20*20).所采用的存储器也将是O(NlogN),其大约为80mb(100000*20*4kb),这太大,因为限制是64mb.

我们如何更快地进行查询并使用更小的空间？

我正试图解决这个问题.

我找到了这个问题的教程但是我没有得到如何构建分段树,它将在O(log n)中找到小于x的数字(x可以改变).在教程中它已被省略.

任何人都可以解释我该怎么做？

给出了一个最初具有一些Max.val值的数组,然后有一些查询在Range L,R中进行更新,这样任何位置的值都是最小的.例如:

Update Range 1 3 with value 3 
Array  3 3 3 Max.val Max.val
Now update 2 and 4 with 1
Array  3 1 1 1 Max.val
Now update 1 and 2 with 2
Array  2 1 1 1 Max.val
i.e update only if(A[i]>value) A[i]=value;

在上面的查询之后我必须显示我的最终结果 array:i.e 2 1 1 1 Max.val

我正在使用Segment Tree来解决这个问题,但我得到了TLE(超出时间限制).我不知道为什么？我的方法是logN. 这是我的更新功能

public static void lets_change(int curr, int[] T, int x, int y, int a, int b, int c) {
    // …

我需要一些帮助来试图找出一些东西:

给定一系列无序数(小于15.000) - A - 我必须回答i,j,x,y形式的Q查询(Q <= 100000),其转换如下:

A中的范围[i,j]中的数字是多于(或等于)x但小于y,且序列中的所有数字都小于5000.

我的印象是这需要类似O(logN)的东西,因为序列的长度很长,这让我想到了BIT(二进制索引树 - 因为查询)但是2D BIT太大而且要求很多即使在更新方面也要运行.所以我在这里看到的唯一解决方案应该是1D BIT或Segment Trees,但我无法想出如何根据这些数据结构制定解决方案.我尝试保留有序数字集中的位置,但我无法弄清楚如何制作响应给定表单查询的BIT.

对于给定的限制,算法也应该适合500ms. 编辑1: 500ms用于预处理和回答查询的所有操作

编辑2:其中i,j是序列A中第一个和最后一个元素的位置,用于查找大于x且小于y的元素

编辑3:示例:让1,3,3,4,6,3和查询1,4,3,5在位置1和4(包括)之间有2个元素(3和4)更大(或相等) )比3小于5

先感谢您!PS:对不起英语不好!

我正在从一组数据中实现段树,我还想在更新数据范围时保持树的最大/最小值.这是我在本教程http://p--np.blogspot.com/2011/07/segment-tree.html之后的初始方法.遗憾的是它并没有在所有的工作中,逻辑对我来说很有意义,但我有点困惑b和e,我不知道这是范围data阵列？或者它是树的实际范围？根据我的理解,max_segment_tree[1]应该保持max范围,[1, MAX_RANGE]同时min_segment_tree[1]应该保持min范围[1, MAX_RANGE].

int data[MAX_RANGE];
int max_segment_tree[3 * MAX_RANGE + 1];
int min_segment_tree[3 * MAX_RANGE + 1];
void build_tree(int position, int left, int right) {
    if (left > right) {
        return;
    }
    else if (left == right) {
        max_segment_tree[position] = data[left];
        min_segment_tree[position] = data[left];
        return;
    }

    int middle = (left + right) / 2;
    build_tree(position * 2, left, middle);
    build_tree(position …

我在理解线段树复杂性方面遇到问题。很明显，如果你有一个只需要更改一个节点的更新函数，那么它的复杂度将为 log(n)。但我不知道为什么查询（a，b）的复杂性是log（n），其中（a，b）是需要检查的区间。谁能为我提供直观/正式的证据来理解这一点？

给定一个大的未排序数组,我需要找出特定范围内给定数字的出现次数.(可以有很多查询)

例如,如果ARR []={ 6,7,8,3,4,1,2,4,6,7,8,9}和left_range=3和right_range=7和number=4,然后输出将是2.(考虑0索引阵列)

arr [i]可以在1到100000的范围内.阵列最多可以有100000个数字.

你能指导我在这里使用哪种数据结构或算法吗？

PS:允许预处理数组.

是否有段树的STL？

在竞争性编程中,需要花费大量时间来编写seg树.我想知道是否有任何STL,以便节省大量时间.

考虑一个数组（基于 0 的索引），我必须找到所有可能范围 [i,n] 的不同元素的总和，其中 0< i < n

例子：

arr={1,2,1,3}

sum_range[0,3]={1,2,3}=6
sum_range[1,3]={1,2,3}=6
sum_range[2,3]={1,3}=4
sum_range[3,3]={3}=3  

O(n^2) 解决方案是一种可能的解决方案，我已经阅读过持久线段树也可以做到这一点，尽管我找不到好的教程。

能否在 O(N^2) 时间内解决？

如果有人指出持久线段树，请解释或提供一些好的链接？