对于给定的n获取{floor（n / 2），n％2，floor（n / 2）}的列表，然后检查给定范围内的1，s数

Question

对于给定的数字n，形成一个列表并将以下模式依次插入到列表中的相同位置。{floor（n / 2），n％2，floor（n / 2）}直到列表中的每个元素都是1或0。现在，计算从1到r的1s数（1索引）。

说明：从n开始。然后列出包含以下元素的列表。 {floor（n / 2），n％2，floor（n / 2）}。现在，此列表包含三个元素。现在进一步分解这三个元素中的每一个，分别考虑将这三个元素分别为INPLACE的floor分别为floor（n / 2），n％2和floor（n / 2）。并且该过程将一直进行到n减小为1或0为止。因此，它将基本上形成一棵树，该树具有3个分支，每个分支从根的1个节点（n）开始在每个级别上都有。输入格式：三个整数n，l，r

Constraints:
0 ≤ n < 10^12, 0 ≤ r - l ≤ 10^6, 1 ≤ l ≤ r

输出格式在给定范围内包含1的数字的单行。

Sample Input
9 6 9

Sample Output
3

如果我尝试存储所有数字，我将用尽内存如何在不访问每个节点的情况下计算范围

Answer 1

该数组可以看作是二叉树的有序序列，如果您应用朴素算法，它也将是递归树。

该二叉树具有以下属性：

• 它是perfect

• 其高度h对应于表示n所需的二进制数。因此，对于9（0b1001），h = 4。

• 它具有2 ^h-1个节点，这也是数组表示形式中元素的数量。

• 在树的深度为[[i]]的节点，都具有相同的值，并对应于n的i ^th最低有效位。我们将此位称为[[n i，并将[1，h]中的_i。

  因此，所有节点的总和是[1，
• h
中

i的2 ^{i-1 n _i}

的总和]，它恰好是n。深度为[[i的节点的左（或右）子树，将对应于
• floor（n / 2

  i）的树。] >

  要查找与索引j
对应的节点（从1开始，则使用^h

二进制数字来表示

j的二进制表示形式（必要时以“ 0”开头） ） 接着只要该表示形式中包含多个“ 1”，则当最左边的数字为“ 0”时选择左边的分支，否则选择右边的分支。然后删除该数字并重复。然后，我们可以确定在向右移动时忽略的每个左子树的值是什么，将1包含在节点本身中，并取这些值的总和。该总数将表示索引j的1个值在左侧

的数量。这又可以用来知道任何范围内的1个值的总数。

变成一种算法，您将获得下面的代码片段。您可以运行它，输入n，i，j的值，然后查看结果总和：

function sumBetween(n, i, j) {
    if (j < i) return sumBetween(n, j, i); // put range in ascending order
    return sumUntil(n, j) - sumUntil(n, i - 1);
}

function sumUntil(n, i) {
    let numDigits = n.toString(2).length;
    let bitMask = 1 << numDigits;
    if (i >= bitMask) i = bitMask - 1; // Reduce i when exceeding the "array" size
    if (i < 0) i = 0;

    let sum = 0;
    for (bitMask >>= 1; i > 0 && bitMask > 0; bitMask >>= 1) {
        let goRight = i & bitMask; // Extract a bit from i
        let nodeValue = n % 2; // Get value at current node of binary tree
        n >>= 1; // Go down one level in the tree
        if (goRight) sum += nodeValue + n; // Add node value and values in omitted left subtree
        i -= goRight; // Clear bit in i
    }
    return sum;
}

// I/O handling
let inputs = document.querySelectorAll("input");
let result = document.querySelector("span");

document.addEventListener("input", refresh);

function refresh() {
    let [n, i, j] = Array.from(inputs, input => input.value).map(Number);
    let sum = sumBetween(n, i, j);
    result.textContent = sum;
}
refresh();

input { width: 4em }

n: <input type="number" value="9"><br>
i: <input type="number" value="6"><br>
j: <input type="number" value="9"><br>
sum: <span></span>

用于获取范围之和的算法的时间复杂度为
O（logn）

，与

i

和

j

的值无关。空间复杂度为O（1）-无需填充数组。