左闭右开神教

日期:
标签: oi trick

前言

缺点:同学读不懂你的代码了

不难发现,在大多数编程语言的标准库中,通常都会以左闭又开,从 0 开始的方式表示区间。本文将论述这种表示方式在算法竞赛中的诸多优势。

注:具体问题具体分析,辩证看待这篇文章。

理解左闭右开

如果表示的数是连续的,自然会有这种区间表示的问题,该开就开,该闭就闭。

然而计算机无法表示连续的数,无论是在实践上还是理论上。能够表示连续的数意味着可以表示两个数 ,使得 ,这显然是做不到的。

因此,计算机在表示数值时,常常会离散化成离散的整数,再用“段”来表示。这就导致了闭区间,开区间,左闭右开,左开右闭四种区间表示方法的混乱。

number line

如图,绿色的数表示计算机中的实际的数,是离散成段的,而蓝色的数表示两个绿色的数之间的分隔。 那么,表示绿色的左闭右开区间 就可以理解成以蓝色的端点 所围起来的区间。这样离散整数的区间 就对应连续实数区间的 ,不需要任何额外转换,更加符合人类的直觉。

蓝色和绿色数就相当于物理上时刻和时间段,编程时一定要厘清两者之间的关系。

如果你是色盲,那么你只需要知道图片上数轴的线是红色的,较高的数字是蓝色的,较低的数字是绿色的就行了。

当然,左闭右开的表示和 C++ 中下标从 0 开始有极大关系。

优势

这些优势是由上面的“离散左闭右开区间与实数的区间对应”,所引出来的。

计算长度

这离散区间的长度就是左右两个端点的距离,由于离散左闭右开区间与连续实数区间天然的对应关系,计算区间 的长度就是 ,无需额外转换。

C++ 中,长度为 数组为 ,正好和左闭右开呼应。

表示空集

可以使左右端点相同来表示空集,如果是闭区间的话,必须要(不优雅地)使右端点小于左端点。这在编写莫队时十分有用。

表示连续区间

由于 可以理解为 端点到 端点,因此表示连续区间端点就应该重合,这在编写分治、线段树之类的代码时十分有用。

实践

环状数组

一个数组长度为 ,那么第 个元素的前一个就是 ,后一个就是

环状数组的下标不能比大小,不能用类似 for (int i = l; i <= r; i = (i + 1) % n) 的方式循环,但用左闭右开表示区间就可以写成 for (int i = l; i != r; i = (i + 1) % n)

前缀和和差分

前缀和可以理解成离散化的积分,差分可以理解为离散化的微分。

对于数列 ,我们定义其前缀和数组:

即前 项的和。

同样我们定义差分数组:

求区间 的和:

区间

实践:

std::vector<int> a(n), s(n + 1), d(n);
for (int i = 0; i < n; i++) s[i + 1] = s[i] + a[i];
for (int i = 1; i < n; i++) d[i] = a[i] - a[i - 1];

注意前缀和数组比原数组的长度大一,且这样定义会使得原数组的差分数组的前缀和数组比原数组多一个 0

仿照前缀和,我们也可以定义出字符串 的前缀哈希:

这样求子串 的哈希就是

各种 dp 数组也可以仿照这种方式定义。

还是那句话:具体问题具体分析,这种定义依然存在许多不方便之处。

二分

在数组 的区间 中找值 出现的位置。

lower_bound:

int l = 0, r = n;
while (l < r) {
    int mid = (l + r) / 2;
    if (a[mid] >= x) r = mid;
    else l = mid + 1;
}
return r;

upper_bound:

int l = 0, r = n;
while (l < r) {
    int mid = (l + r) / 2;
    if (a[mid] > x) r = mid;
    else l = mid + 1;
}
return r;

两份代码唯一的区别在于:一个是 a[mid] >= x,一个是 a[mid] > x

挺没用的

树状数组

树状数组可以下标从 0 开始,通过简单的找规律发现,x 的父节点是 x | (x + 1),能管辖的范围是 x & (x + 1)x,不需要依赖 lowbit。可以写出如下代码:

struct fenwick_tree
{
    int n;
    std::vector<int> t;
    fenwick_tree(int n) : n(n), t(n) {}
    void add(int x, int v)
    {
        for (; x < n; x |= (x + 1)) t[x] += v;
    }
    int sum(int x)
    {
        int res = 0;
        for (x--; x >= 0; x = (x & (x + 1)) - 1) res += t[x];
        return res;
    }
};

然而这样很没有必要,也容易背错,你也可以写传统的下标从 1 开始的树状数组再封装成下标从 0 开始:

struct fenwick_tree
{
    int n;
    std::vector<int> t;
    fenwick_tree(int n) : n(n), t(n) {}
    void add(int x, int v)
    {
        for (x++; x <= n; x += x & -x) t[x - 1] += v;
    }
    int sum(int x)
    {
        int res = 0;
        for (; x >= 1; x -= x & -x) res += t[x - 1];
        return res;
    }
};

注意这里两个 fenwick_tree::sum 都表示 的和,与前面前缀和的定义吻合。

类比前面前缀和和差分,可以容易得出单点修改区间查询和单点修改区间查询的代码。

对于区间修改区间查询,则和常规思路一致,假设 的差分数组为 ,则:

容易发现这个结论明显比普通的树状数组优美,没有了奇怪的 +1。

代码(LibreOJ 提交记录):

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    std::vector<long long> a(n), d(n), di(n);

    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    d[0] = a[0];
    di[0] = 0;

    for (int i = 1; i < n; i++) {
        d[i] = a[i] - a[i - 1];
        di[i] = d[i] * i;
    }

    fenwick_tree f(d), fi(di);

    while (q--) {
        char op;
        scanf(" %1c", &op);

        if (op == '2') {
            int l, r;
            scanf("%d%d", &l, &r);
            l--;
            auto ans = f.sum(r) * r - fi.sum(r) - f.sum(l) * l + fi.sum(l);
            printf("%lld\n", ans);
        } else if (op == '1') {
            long long l, r, v;
            scanf("%lld%lld%lld", &l, &r, &v);
            l--;
            f.add(l, v);
            f.add(r, -v);
            fi.add(l, v * l);
            fi.add(r, -v * r);
        }
    }
}

没有奇怪的 +1 -1,舒服!

线段树

堆式存储线段树也可以让下标从 0 开始。具体来说节点 x 的左儿子为 x * 2 + 1,右儿子为 x * 2 + 2,当然我觉得这很不优美,不如下标从 1 开始。

重点是区间表示,左闭右开的区间意味着连续区间的左右端点一致,如下面常见的 add_tree 函数(用于线段树区间加):

 void add_tree(int l, int r, long long x, int ll, int rr, int p)
 {
     if (l <= ll && rr <= r) {
         put_tag(x, ll, rr, p);
         return ;
     }
     spread_tag(ll, rr, p);
     int mid = (ll + rr) / 2, lchild = p * 2, rchild = p * 2 + 1;
     if (l < mid) add_tree(l, r, x, ll, mid, lchild);
     if (mid < r) add_tree(l, r, x, mid, rr, rchild);
     t[p].sum = t[lchild].sum + t[rchild].sum;
 }

完整代码 LibreOJ 提交记录

注意到代码往下递归的那两行,得益于左闭右开的优点,这里对齐了!再看其他的线段树模板,无法对齐,丑陋不堪。

分块

判断区间在哪一块是明显方便许多,可以直接取模相除: LibreOJ 提交记录

总结

具体问题具体分析,没有什么是完美的,上述内容依然存在不优雅之处,比如倒序遍历时左开右闭明显比左闭右开好用。一定要区分清楚数和边界的关系,也要注意题目给的是哪种区间表示,自己代码又用的是哪种区间表示,不能混淆。