标签: segment-tree

好吧,我试图在Codechef上解决这个翻转硬币问题.用分段树解决它.但是时间限制超过了.我搜索并发现我必须使用懒惰传播.但我无法理解.我的更新功能递归地工作(从上到下).请提供一些提示或用例子解释.还要指出我必须更改代码的位置.

在翻转硬币时,如果节点值为1,则在更新期间将其更改为0,如果为0,则将其更改为1.

start和end是原始数组的限制.树是分段树阵列.

void update(int node, int start, int end,int pos)//pos=position to update
{
    if(start==end) tree[node]=(tree[node]==0) ? 1 : 0;
    else
    {
        int mid=(start+end)/2;
        if(mid>=pos) update(2*node + 1, start, mid, pos);
        else update(2*node + 2, mid+1, end, pos);

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

我有一个数组到10个数字消除A [10] = {1,2,3,4,5,6,7,8,9,10}我必须计算特定范围内的数字乘法但不得正确的答案,我正在使用段树,不知道如何使用查询操作这是我的代码:

#include<stdio.h>
#define m 1000000000
#define MAX 100010

typedef unsigned long long ull;
ull a[MAX];
ull tree[4*MAX];

void build_tree(int n,int b,int e){
    if(b>e)return ;
    else if(b==e){
        tree[n] = a[b];
        return ;
    }
    build_tree(n*2,b,(b+e)/2);
    build_tree(n*2+1,(b+e)/2+1,e);
    tree[n] =( tree[n*2]%m * tree[n*2 + 1]%m )%m;
}


ull query(int index, int ss, int se, int qs, int qe)
  {
      ull p1, p2,p;
      if (qs > se || qe < ss)
          return -1;

      if (ss >= qs && se <= qe)
          return …

正如我从资料中读到的那样，我了解到 当二维矩阵只有一维时，四叉树的最坏情况复杂度是 O(N)。我无法理解其中的原因。例如。当矩阵只有 1xm 时，我们将继续将其分成两半，并在 log(m) 停止时到达单位单元。所以复杂度应该是 log(m) 谢谢

我想知道解决这个问题的有效方法：

给定具有左上角和右下角的 N 个矩形，请找出 N 个矩形的并集的周长。

我只有O(N^2)算法而且太慢了，所以请找到更有效的算法。

您可以假设坐标值为正整数且小于 100000。

编辑：例如，在这种情况下，周长是 30。

一个 O(n^2) 算法：

for x=0 to maxx
   for i=0 to N
      if lowx[i] = x
         for j=lowy[i] to highy[i]
            d[j]++
            if d[j] = 1 then ret++
      if highy[i] = x
         for j=lowy[i] to highy[i]
            d[j]--
            if d[j] = 0 then ret++
   for y=0 to maxy
      if d[y] = 0 && d[y + 1] >= 1 then ret++
      if d[y] >= 1 && d[y + 1] = 0 …

https://cses.fi/problemset/task/1143/

我正在尝试解决这个问题，我使用线段树来解决它。我尝试了所有可能的测试用例，但它没有被接受。

只是在一个太大的测试用例中失败了。请帮我解决这个问题..！！！

解决方案：https://cses.fi/paste/072a5f07ec4a533b18c669/

给定一个包含 n 个整数的数组，索引从 1->n。任务是执行 Q 次给定的查询，并在每次查询后打印数组的总和。

我们可以执行三种类型的操作：

• 1 X：将 X 添加到数组中（其索引将为 n+1、n+2、...）
• 2 Y：从数组中删除索引为 Y 的元素
• 3 Z：对数组中的每个元素i，执行i^Z(i xor Z)

例子：

输入arr[] = {2, 3, 9, 5, 6, 6}, Q = 5

1 3

3 5

2 2

3 2

2 7

输出： 34 37 31 27 23

说明：

1 3 -> arr[] = {2, 3, 9, 5, 6, 6, 3} -> 总和 = 34

3 5 -> arr[] = {7, 6, …

这个问题的链接是UVA - 1394:还有一个.
朴素算法是扫描整个数组并在每次迭代时标记第k个元素,最后停止:这需要O(n ^ 2)时间.
我已经搜索了另一种算法并且遇到了一个中文博客,该博客指出我使用惰性传播将树分割为O(N lgN)时间的解决方案.
在研究了分段树后,我尝试形成一个O(N lgN)时间的算法,但无济于事.

给定N个工作,其中每个工作由以下三个元素表示.

1)开始时间

2)完成时间.

3)利润或价值相关.

找到作业的最大利润子集,使子集中没有两个作业重叠.

我知道一个动态编程解决方案,其复杂度为O(N ^ 2)(接近LIS,我们必须检查以前的元素,我们可以合并当前间隔并采用合并给出最大值的区间直到第i个这个解决方案可以使用二进制搜索和简单排序进一步改进为O(N*log N)!

但是我的朋友告诉我,甚至可以通过使用Segment Trees和二分搜索来解决它!我不知道我将在哪里使用Segment Tree以及如何使用.

你能帮我吗？

根据要求,抱歉没有评论

我正在做的是根据起始索引进行排序,通过合并先前的时间间隔和它们的最大可获得值,将最大可获得值存储到DP [i]中i!

 void solve()
    {
        int n,i,j,k,high;
        scanf("%d",&n);
        pair < pair < int ,int>, int > arr[n+1];// first pair represents l,r and int alone shows cost
        int dp[n+1]; 
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            scanf("%d%d%d",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
        std::sort(arr,arr+n); // by default sorting on the basis of starting index
        for(i=0;i<n;i++)
        {
            high=arr[i].second;
            for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
            {
                if(arr[i].first.first>=arr[j].first.second)  
                        high=std::max(high …

我正在尝试使用Segment Tree 来解决频繁的值

这篇博客文章使用了类似的方法

我想将列表分成以下间隔:

-1 -1 1 1 1 1 3 10 10 10 变 (0, 2) (2, 6) (6, 7), (7, 10)

我有一个代码:

g s = map (\x->(head x, length x)) . group . sort $ s

但它没有给出正确的输出.

是否可以使用频繁的值？