间隔和更新与除数之和-yiteyi-C++库

给定一个由N个整数组成的数组。你必须回答两类问题： 1.更新[l，r]——对于从l到r范围内的每个i，更新A _我带D（A） _我 )，其中D（A） _我 )表示一个元素的除数 _我 2.查询[l，r]——计算数组A中l和r之间的所有数字之和。输入以两个整数N和Q给出，分别表示数组中的整数数和查询数。下一行包含一个由n个整数组成的数组，后跟Q个查询，其中第i个查询表示为type _我 L _我 R _我 .

null

先决条件： 二叉索引树 | 分段树

例如：

Input : 7 4
        6 4 1 10 3 2 4
        2 1 7
        2 4 5
        1 3 5
        2 4 4
Output : 30
         13
         4

说明： 第一个查询是从一个 _1. 到 _7. 也就是6+4 + 1 + 10 + 3 + 2 + 4 = 30. 同样，第二次查询的结果为13。对于第三个问题，这是更新操作，因此 _3. 将保持1，A _4. 将成为4岁半 _5. 将变成2。第四个查询将生成一个 _4. = 4.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法： 一个简单的解决方案是运行一个从l到r的循环，并计算给定范围内元素的总和。要更新一个值，预先计算每个数的除数的值，只需执行arr[i]=除数[arr[i]]。

有效方法： 其思想是降低每个查询的时间复杂度，并将操作更新为O（logN）。使用二进制索引树（位）或段树。构造一个BIT[]数组，有两个查询和更新操作函数，并预计算每个数的除数。现在，对于每个更新操作，关键的观察是，数字“1”和“2”将分别以“1”和“2”作为其除数，因此如果它存在于更新查询范围内，则不需要更新它们。我们将使用一个集合来存储大于2的数字的索引，并使用二进制搜索来查找更新查询的l索引，并递增l索引，直到更新查询范围内的每个元素都被更新。如果arr[i]只有2个除数，那么在更新它之后，将其从集合中删除，因为即使在任何下一次更新查询之后，它也将始终为2。对于求和查询操作，只需执行查询（r）–查询（l–1）。

                     // CPP program to calculate sum                   
                     // in an interval and update with                   
                     // number of divisors                   
                     #include <bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     int                               divisors[100], BIT[100];                   
                             
                     // structure for queries with members type,                   
                     // leftIndex, rightIndex of the query                   
                     struct                               queries                   
                     {                   
                                         int                               type, l, r;                   
                     };                   
                             
                     // function to calculate the number                   
                     // of divisors of each number                   
                     void                               calcDivisors()                   
                     {                   
                                         for                               (                               int                               i = 1; i < 100; i++) {                   
                                         for                               (                               int                               j = i; j < 100; j += i) {                   
                                         divisors[j]++;                   
                                         }                   
                                         }                   
                     }                   
                             
                     // function for updating the value                   
                     void                               update(                               int                               x,                               int                               val,                               int                               n)                   
                     {                   
                                         for                               (x; x <= n; x += x&-x) {                   
                                         BIT[x] += val;                   
                                         }                   
                     }                   
                             
                     // function for calculating the required                   
                     // sum between two indexes                   
                     int                               sum(                               int                               x)                   
                     {                   
                                         int                               s = 0;                   
                                         for                               (x; x > 0; x -= x&-x) {                   
                                         s += BIT[x];                   
                                         }                   
                                         return                               s;                   
                     }                   
                             
                     // function to return answer to queries                   
                     void                               answerQueries(                               int                               arr[], queries que[],                               int                               n,                               int                               q)                   
                     {                   
                                         // Declaring a Set                   
                                         set<                               int                               > s;                   
                                         for                               (                               int                               i = 1; i < n; i++) {                   
                             
                                         // inserting indexes of those numbers                   
                                         // which are greater than 2                   
                                         if                               (arr[i] > 2) s.insert(i);                   
                                         update(i, arr[i], n);                   
                                         }                   
                             
                                         for                               (                               int                               i = 0; i < q; i++) {                   
                             
                                         // update query                   
                                         if                               (que[i].type == 1) {                   
                                         while                               (                               true                               ) {                   
                             
                                         // find the left index of query in                   
                                         // the set using binary search                   
                                         auto                               it = s.lower_bound(que[i].l);                   
                             
                                         // if it crosses the right index of                   
                                         // query or end of set, then break                   
                                         if                               (it == s.end() || *it > que[i].r)                               break                               ;                   
                             
                                         que[i].l = *it;                   
                             
                                         // update the value of arr[i] to                   
                                         // its number of divisors                   
                                         update(*it, divisors[arr[*it]] - arr[*it], n);                   
                             
                                         arr[*it] = divisors[arr[*it]];                   
                             
                                         // if updated value becomes less than or                   
                                         // equal to 2 remove it from the set                   
                                         if                               (arr[*it] <= 2) s.erase(*it);                   
                             
                                         // increment the index                   
                                         que[i].l++;                   
                                         }                   
                                         }                   
                             
                                         // sum query                   
                                         else                               {                   
                                         cout << (sum(que[i].r) - sum(que[i].l - 1)) << endl;                   
                                         }                   
                                         }                   
                     }                   
                             
                     // Driver Code                   
                     int                               main()                   
                     {                   
                                         // precompute the number of divisors for each number                   
                                         calcDivisors();                   
                             
                                         int                               q = 4;                   
                             
                                         // input array                   
                                         int                               arr[] = {0, 6, 4, 1, 10, 3, 2, 4};                   
                                         int                               n =                               sizeof                               (arr) /                               sizeof                               (arr[0]);                   
                             
                                         // declaring array of structure of type queries                   
                                         queries que[q + 1];                   
                             
                                         que[0].type = 2, que[0].l = 1, que[0].r = 7;                   
                                         que[1].type = 2, que[1].l = 4, que[1].r = 5;                   
                                         que[2].type = 1, que[2].l = 3, que[2].r = 5;                   
                                         que[3].type = 2, que[3].l = 4, que[3].r = 4;                   
                             
                                         // answer the Queries                   
                                         answerQueries(arr, que, n, q);                   
                             
                                         return                               0;                   
                     }                   

输出：

30
13
4

回答Q查询的时间复杂度为O（Q*log（N））。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章