范围最小查询和间隔更新 [英] Range minimum query and update for intervals

问题描述

我需要一个支持三种操作的范围最小查询数据结构:
 -使用数组A [n]
初始化  -update(i，j，v)-将v添加到范围A [i] ... A [j]
中的所有元素  -查询(i，j)-从范围A [i] ... A [j]

I need a range minimum query data structure that supports three operations:
 - initialize with array A[n]
 - update(i,j,v) - add v to all elements from the range A[i]...A[j]
 - query (i,j) - find the minimal element from the range A[i]...A[j]

更新和查询都必须在O(log n)时间内运行，并且结构必须占用O(n)空间.

Both update and query must run in O(log n) time and the structure must take O(n) space.

推荐答案

感谢您的帮助！
我设法通过Lazy Propagation技术做到了这一点.

Thanks for the help!
I managed to do this with the Lazy Propagation technique.

初始化使用向量而不是数组.
很容易变成最大查询结构...将所有min-s替换为max-s，并将数字2100000000替换为-2100000000

The initialization is with a vector instead of an array.
It is easy to be turned into a maximum query structure... replace all the min-s with max-s and the number 2100000000 with -2100000000

#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

class IntervalTree
{
    int* tree;
    int* lazy;
    int n;

    void build_tree(const vector<int>& v, int node, int a, int b)
    {
        if (a > b) return;

        if (a == b) { tree[node] = v[a]; return; }

        build_tree(v, node * 2, a, (a + b) / 2);
        build_tree(v, node * 2 + 1, 1 + (a + b) / 2, b);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    void update_lazy(int node, int a, int b)
    {
        tree[node] += lazy[node];

        if (a != b) 
        { 
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }

        lazy[node] = 0;
    }

    void update_tree(int node, int a, int b, int i, int j, int value)
    {
        if (lazy[node] != 0) update_lazy(node,a,b);

        if (a > b || a > j || b < i) return;

        if (a >= i && b <= j) 
        {
            tree[node] += value;
            if (a != b) 
            {
                lazy[node * 2] += value;
                lazy[node * 2 + 1] += value;
            }
            return;
        }

        update_tree(node * 2, a, (a + b) / 2, i, j, value);
        update_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j, value);

        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    int query_tree(int node, int a, int b, int i, int j)
    {
        if (a > b || a > j || b < i) return 2100000000;

        if (lazy[node] != 0) update_lazy(node,a,b);

        if (a >= i && b <= j) return tree[node];

        int q1 = query_tree(node * 2, a, (a + b) / 2, i, j);
        int q2 = query_tree(1 + node * 2, 1 + (a + b) / 2, b, i, j);

        return min(q1, q2);
    }

public:
    IntervalTree(const vector<int>& v)
    {
        n = v.size();

        int s = 2*pow(2, ceil(log2(v.size())));

        tree = new int[s];

        lazy = new int[s];

        memset(lazy, 0, sizeof lazy);

        build_tree(v, 1, 0, n - 1);
    }

    void update(int idx1, int idx2, int add)
    {
        update_tree(1, 0, n - 1, idx1, idx2, add);
    }

    int query(int idx1, int idx2)
    {
        return query_tree(1, 0, n - 1, idx1, idx2);
    }
};

这篇关于范围最小查询和间隔更新的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！