树状数组求解前缀最大值
树状数组可以求解和前缀区间有关的问题,例如前缀和,前缀区间最值.
可以利用
l
o
g
n
log_n
logn的时间复杂度快速查找前缀信息.
利用树状数组查询前缀区间中最大值问题.
树状数组下标1位置存储arr数组下标1位置的最大值.
树状数组2位置存储arr数组1,2位置最大值.
数组数组3位置存储arr数组3位置最大值.
以此类推…
查找arr数组1~i前缀区间最大值.利用lowbit跳转,记录遍历的每一个tree[i]的最大值.
lowbit跳转,while(i<tree.size()),i+=lowbit(i),i会遍历所有拥有i位置的数组数组位置.
while(i>0)i-=lowbit(i),i会遍历所有能够组成1,2,3…i的树状数组位置.
如果i位置是7,lowbit往前跳转,树状数组会遍历4,6,7位置,对应arr组成1,2,3,4,5,6,7.
往后跳转,树状数组会遍历7,8,拥有arr中7位置的树状数组位置.
#include<bits/stdc++.h>
using namespace std;
#define int long long // 定义 int 为 long long 类型，方便处理大数
#define endl '\n' // 定义 endl 为换行符，方便输出
vector<int> arr = { 1, 4, 2, 5, 3, 5, 6, 3, 2, 5 }; // 定义一个全局数组并初始化
// 树状数组类定义
class Tree {
public:
vector<int> tree; // 定义一个向量 tree，用于存储树状数组
// 计算 lowbit
int lowbit(int i) {
return i & -i; // 返回 i 和 -i 的按位与，获取最低位的 1
}
// 在位置 i 处更新值 v
void sett(int i, int v) {
while (i <= tree.size()) { // 从索引 i 开始，向上更新树状数组
tree[i] = max(tree[i], v); // 更新节点为当前值和新值的最大值
i += lowbit(i); // 移动到下一个需要更新的位置
}
}
// 查询前缀 [1, i] 的最大值
int gett(int i) {
int ret = LLONG_MIN; // 初始化结果为负无穷大
while (i > 0) { // 从索引 i 开始，向下计算前缀最大值
ret = max(tree[i], ret); // 更新结果为当前值和当前结果的最大值
i -= lowbit(i); // 移动到下一个需要计算的位置
}
return ret; // 返回前缀最大值
}
// 默认构造函数
Tree() {}
// 使用给定大小 n 初始化树状数组
Tree(int n) {
tree.assign(n + 3, 0); // 初始化树状数组大小，并将值设为 0
}
// 使用给定数组初始化树状数组
Tree(vector<int> arr) {
tree.assign(arr.size() + 3, LLONG_MIN); // 初始化树状数组大小，并将值设为负无穷大
int i = 1;
for (auto& xx : arr) {
sett(i++, xx); // 将数组中的值添加到树状数组中
}
}
};
Tree t1(arr); // 使用全局数组初始化树状数组 t1
int q; // 定义查询次数
// 主解题函数
void solve() {
for (auto& xx : arr) {
cout << xx << " "; // 输出数组中的每个元素
}
cout << endl;
for (int i = 0; i < arr.size(); i++) {
cout << i << " "; // 输出数组的索引
}
cout << endl;
cin >> q; // 读取查询次数
for (int i = 1; i <= q; i++) {
int k;
cin >> k; // 读取查询索引
k++;
cout << t1.gett(k) << endl; // 输出前缀 [1, k] 的最大值
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 快速输入输出
solve(); // 调用解题函数
}
673. 最长递增子序列的个数
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。提示:
1 < = n u m s . l e n g t h < = 2000 1 <= nums.length <= 2000 1<=nums.length<=2000
− 1 0 6 < = n u m s [ i ] < = 1 0 6 -10^6 <= nums[i] <= 10^6 −106<=nums[i]<=106
countt数组,对应arr数组每一个元素.
countt存储node类型,node类型有两个变量,maxlen和count.
countt[i].maxlen表示arr数组中以i位置元素为结尾的最长递增子序列的长度,countt[i].count表示arr数组中以i位置元素为结尾的最长递增子序列的个数.
如果countt数组维护完,只需要直到最长递增子序列的长度,然后遍历countt数组,统计是最长递增子序列长度的个数即可.
填写countt[i]位置的数据,需要直到1~i-1区间中,元素值小于arr[i]的最长递增子序列的长度,以及个数.
元素值小于arr[i],对应词频表,元素值映射个数,词频.元素值作为下标,刚好是排序好的,也就是求前缀和.
1~i-1,对应依次遍历.
利用树状数组存储以某元素值为结尾的最长递增子序列的长度,元素值映射最长的长度.
index映射arr,元素值映射index,index映射maxlen.
利用map做离散化处理.
利用树状数组查询1~i-1以小于arr[i]元素结尾的最长递增子序列的长度.
然后遍历arr数组,统计数量.维护当前位置countt.
Tree中gett函数获取1~i最大值,但是如果进来的i是0,直接返回0,最大长度不存在.因为外面要用这个最大长度+1表示当前的最大长度.
struct node {
int maxlen = 1, count = 0; // 定义节点结构，包含最大长度和计数
};
class Tree {
public:
vector<int> tree; // 定义一个向量 tree，用于存储树状数组
// 计算 lowbit
int lowbit(int i) {
return i & -i; // 返回 i 和 -i 的按位与，获取最低位的 1
}
// 在位置 i 处更新值 v
void sett(int i, int v) {
while (i < tree.size()) { // 从索引 i 开始，向上更新树状数组
tree[i] = max(tree[i], v); // 更新节点为当前值和新值的最大值
i += lowbit(i); // 移动到下一个需要更新的位置
}
}
// 查询前缀 [1, i] 的最大值
int gett(int i) {
int ret = INT_MIN; // 初始化结果为负无穷大
if (i == 0) // 如果索引为 0
return 0; // 返回 0
while (i > 0) { // 从索引 i 开始，向下计算前缀最大值
ret = max(ret, tree[i]); // 更新结果为当前值和当前结果的最大值
i -= lowbit(i); // 移动到下一个需要计算的位置
}
return ret; // 返回前缀最大值
}
// 默认构造函数
Tree() {}
};
class Solution {
public:
Tree t1; // 定义一个树状数组对象 t1
vector<int> arr; // 定义一个向量 arr，用于存储输入的数组
map<int, int> arr_index; // 定义一个 map，用于存储数组元素的索引
vector<node> countt; // 定义一个向量 countt，用于存储每个位置的节点信息
int ret = 0; // 定义一个变量 ret，用于存储结果
int maxnlen = 0; // 定义一个变量 maxnlen，用于存储最大长度
// 主解题函数
void solve() {
maxnlen = 0; // 初始化最大长度为 0
ret = 0; // 初始化结果为 0
arr_index.clear(); // 清空索引 map
for (auto& x : arr) { // 遍历输入数组
arr_index[x]; // 在 map 中记录每个元素
}
int index = 1;
for (auto& x : arr_index) { // 给每个元素分配唯一的索引
x.second = index++;
}
countt.assign(arr.size(), node()); // 初始化 countt 向量
t1.tree.assign(index, 0); // 初始化树状数组
for (int i = 0; i < arr.size(); i++) { // 遍历数组
int index = arr_index[arr[i]]; // 获取当前元素的索引
int maxlen = t1.gett(index - 1); // 获取当前索引之前的最大长度
int ans = 0;
for (int j = 0; j < i; j++) { // 遍历之前的元素
if (countt[j].maxlen == maxlen && arr[j] < arr[i]) { // 找到符合条件的元素
ans += countt[j].count; // 累加计数
}
}
countt[i].maxlen = maxlen + 1; // 更新当前元素的最大长度
countt[i].count = max(ans, 1); // 更新当前元素的计数
t1.sett(index, countt[i].maxlen); // 在树状数组中更新当前元素的最大长度
maxnlen = max(maxnlen, countt[i].maxlen); // 更新最大长度
}
for (int i = 0; i < countt.size(); i++) { // 遍历 countt 向量
if (countt[i].maxlen == maxnlen) { // 找到最大长度的元素
ret += countt[i].count; // 累加结果
}
}
}
// 查找最长递增子序列的数量
int findNumberOfLIS(vector<int>& _nums) {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 快速输入输出
arr = _nums; // 将输入数组赋值给 arr
solve(); // 调用解题函数
return ret; // 返回结果
}
};
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！