当前位置： 首页 > news >正文

网站建设 业务板块名称电子商务网店运营推广

news 2025/8/7 2:54:29
网站建设 业务板块名称,电子商务网店运营推广,百度经验官网,中国菲律宾关系现状前言 看这篇文章前我建议你们先看这个视频还有这个视频，不然你们可能看不懂。 一、树状数组的核心思想与本质 核心思想：树状数组（Fenwick Tree）是一种用于高效处理前缀和查询和单点更新的数据结构。 本质：通过二进…

前言

看这篇文章前我建议你们先看这个视频还有这个视频，不然你们可能看不懂。
在这里插入图片描述

一、树状数组的核心思想与本质

核心思想：树状数组（Fenwick Tree）是一种用于高效处理前缀和查询和单点更新的数据结构。
本质：通过二进制索引和树形结构，将前缀和的计算复杂度从

O(n) 优化到 O(logn)。

二、树状数组的基本操作

  1. 初始化
    初始化一个大小为 n 的数组，所有元素初始值为 0。

  2. 单点更新
    更新某个位置的值，并维护树状数组的结构。

  3. 前缀和查询
    查询从第一个元素到某个位置的前缀和。

  4. 区间和查询
    查询某个区间的和。

三、树状数组的应用场景

动态前缀和查询：

实时查询数组的前缀和，支持单点更新。

示例：LeetCode 307. 区域和检索 - 数组可修改。

逆序对计数：

使用树状数组统计数组中逆序对的数量。

示例：LeetCode 493. 翻转对。

区间更新与单点查询：

通过差分数组和树状数组实现区间更新和单点查询。

示例：LeetCode 370. 区间加法。

二维树状数组：

处理二维数组的前缀和查询和单点更新。

示例：LeetCode 308. 二维区域和检索 - 可变。

四、树状数组的复杂度分析
时间复杂度
单点更新：
O(logn)。

前缀和查询：
O(logn)。

区间和查询：
O(logn)。

空间复杂度
存储树状数组：
O(n)。

五、树状数组的优化技巧

  1. 差分数组
    通过差分数组实现区间更新和单点查询。

  2. 离散化
    在数据范围较大时，使用离散化减少树状数组的大小。

  3. 多维扩展
    将树状数组扩展到二维或更高维度，处理多维数组的前缀和查询和单点更新。

六、常见误区与调试技巧

  1. 误区一：树状数组适用于所有区间查询问题
    澄清：树状数组适用于前缀和查询和单点更新，对于复杂的区间查询问题可能需要其他数据结构（如线段树）。

  2. 误区二：树状数组的初始化复杂度高
    澄清：树状数组的初始化复杂度为 O(nlogn)，但可以通过线性初始化优化到 O(n)。

  3. 调试方法
    打印树状数组：在每次操作后输出树状数组的内容，检查是否正确。

可视化树结构：手动画出树状数组的结构，模拟操作过程。

七、代码模版

单点更新

例题 【模板】树状数组 1

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowbit(int x);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx,T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowbit(int x) {return x & (-x);
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowbit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowbit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}int main() {int n, m;cin >> n >> m;FenwickTree<int> ft(n);for (int i = 1; i <= n; i++) {int x;cin >> x;ft.update(i, x);}while (m--) {int z, x, y;cin >> z >> x >> y;if (z == 1) {ft.update(x, y);}else {int sum = ft.query(x, y);cout << sum << endl;}}return 0;
}

区间更新

例题 【模板】树状数组

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);void update(int idx, T val);T query(int idx);T query(int l, int r);
public:FenwickTree(int n):m_tree(n+2,0){}void updateInterval(int l, int r, T val);T queryIndex(int idx);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val) {int n = (int)m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}template<class T>
void FenwickTree<T>::updateInterval(int l, int r, T val) {update(l, val);update(r + 1, -val);
}template<class T>
T FenwickTree<T>::queryIndex(int idx) {return query(idx);
}int main() {int n, m;cin >> n >> m;FenwickTree<int>ft(n);for (int i = 1; i <= n; i++) {int a;cin >> a;ft.updateInterval(i, i, a);}while (m--) {int opt;cin >> opt;if (opt == 1) {int l, r, x;cin >> l >> r >> x;ft.updateInterval(l, r, x);}else {int k;cin >> k;cout << ft.queryIndex(k) << endl;}}return 0;
}

八、经典例题

排序

#include<iostream>
#include<vector>
using namespace std;template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n, m;cin >> n;FenwickTree<long long>ft(maxn);for (int i = 0; i < n; i++) {cin >> a[i];}long long sum = 0;for (int i = n - 1; i >= 0; i--) {		//逆序遍历数组看看后面有多少个比当前这个值小的个数，乘于它本身累加起来ft.update(a[i], 1);sum += (long long)ft.query(a[i] - 1) * a[i];	//求1~a[i]-1元素个数}cout << sum << endl;return 0;
}

逆序对的数量

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define maxn 1000001
int a[maxn];int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//树状数组的序号是从1开始，利用离散化给原数组每个值标记它的序号，也就是排序好它们的大小}long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);sum += ft.query(a[i] - 1);		//查询1~a[i]-1的元素和，他要找的是比它本身小的个数}cout << sum << endl;return 0;
}

三元组个数

这题就是遍历到的原数组的每一个元素用左边比它小的个数乘于右边比它大的个数，但是复杂度还是太高了，所以还得需要离散化数组，用树状数组记录比它小或大的个数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class T>
class Dicretizer {
private:vector<T>m_data;
public:void addData(T v);void process();int get(T v) const;int size() const;
};template<class T>
void Dicretizer<T>::addData(T v) {m_data.push_back(v);
}template<class T>
void Dicretizer<T>::process() {sort(m_data.begin(), m_data.end());int lastId = 0;for (int i = 1; i < m_data.size(); i++) {T x = m_data[i];if (x != m_data[lastId]) {m_data[++lastId] = x;}}while (lastId < m_data.size() - 1) {m_data.pop_back();}
}template<class T>
int Dicretizer<T>::get(T v) const {int l = -1, r = m_data.size();while (l + 1 < r) {int mid = (l + r) / 2;if (m_data[mid] >= v)r = mid;else l = mid;}if (r == m_data.size() || m_data[r] != v)return -1;return r;
}template<class T>
int Dicretizer<T>::size() const {return m_data.size();
}template<class T>
class FenwickTree {
private:vector<T>m_tree;int lowBit(int idx);
public:FenwickTree(int n):m_tree(n+1,0){}void update(int idx, T val);T query(int idx);T query(int l, int r);
};template<class T>
int FenwickTree<T>::lowBit(int idx) {return idx & -idx;
}template<class T>
void FenwickTree<T>::update(int idx, T val){int n = m_tree.size();while (idx < n) {m_tree[idx] += val;idx += lowBit(idx);}
}template<class T>
T FenwickTree<T>::query(int idx) {T sum = 0;while (idx > 0) {sum += m_tree[idx];idx -= lowBit(idx);}return sum;
}template<class T>
T FenwickTree<T>::query(int l, int r) {return query(r) - query(l - 1);
}#define mod 998244353
#define maxn 1000001
int a[maxn], lt[maxn];	//lt[i]表示小于a[i]的个数int main() {int n;cin >> n;Dicretizer<int>d;FenwickTree<int>ft(n);for (int i = 0; i < n; i++) {cin >> a[i];d.addData(a[i]);}d.process();	for (int i = 0; i < n; i++) {a[i] = d.get(a[i]) + 1;		//树状数组的序号是从1开始，利用离散化给原数组每个值标记它的序号，也就是排序好它们的大小}for (int i = 0; i < n; i++) {ft.update(a[i], 1);lt[i] = ft.query(a[i] - 1);}ft = FenwickTree<int>(n);long long sum = 0;for (int i = n - 1; i >= 0; i--) {ft.update(a[i], 1);int gt = ft.query(a[i] + 1, n);		//求出比a[i]大的个数sum += (long long)lt[i] * gt % mod;sum %= mod;		//sum这个值可能超出范围所以还要取模}cout << sum << endl;return 0;
}

九、总结与学习建议

  1. 核心总结
    树状数组是一种高效处理前缀和查询和单点更新的数据结构。

通过二进制索引和树形结构，将复杂度优化到 O(logn)。

  1. 学习建议
    分类刷题：按问题类型集中练习（如动态前缀和、逆序对计数、区间更新）。

理解算法原理：掌握树状数组的实现步骤和优化技巧。

手写模拟过程：在纸上画出树状数组的结构，模拟操作过程，加深直观理解。

通过以上分析，树状数组作为一种高效的数据结构，在算法竞赛和实际应用中具有广泛用途。掌握其核心思想和实现技巧，能够有效提升算法效率。
在这里插入图片描述
希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
在这里插入图片描述

http://www.cadmedia.cn/news/3073.html

相关文章：

  • b2b平台系统建设seo营销专员
  • 建设部网站 防火规范怎么申请自己的网络平台
  • 网站建设需要的软件营销课程培训视频
  • 工商网站网络推广的方法和技巧
  • 天津市建设管理委员会网站广东: 确保科学精准高效推进疫情
  • 动漫设计与制作主要学什么某一网站seo策划方案
  • 个人备案可以做影视网站吗站长之家查询
  • 隆昌住房和城乡建设官方网站seo整站优化一年价格多少
  • 微信小程序制作多少钱seosem顾问
  • 大丰建站微信如何投放广告
  • 网站建设预算方案模板推广软文发布平台
  • 完善网站建设的目的是搜索引擎的设计与实现
  • 浅谈网站页面框架设计万网域名官网
  • 网站建设工资 优帮云百度网盘首页
  • 成都比较好的网站制作公司谷歌商店paypal官网
  • 自适应企业网站用什么框架做中国培训网的证书含金量
  • aipage网站建设千万不要学网络营销
  • 单页营销型网站东莞seo网站优化排名
  • 上海市网站建设公叿免费制作网页的网站
  • 企业网站建设原则承德网络推广
  • dnf做任务解除制裁网站临沂seo公司稳健火星
  • wordpress 非插件导航分页windows优化大师的特点
  • 网站开发网站排名优化建站
  • 广州网站建设定制费用百度推广是做什么的
  • 营销渠道策略南宁seo怎么做优化团队
  • 网站建设 精品课程seo百度站长工具查询
  • 网站制作设计教程广告优化师工作内容
  • 小微企业名录查询官网seo怎么才能优化好
  • 天津 网站建设色盲测试
  • 医院网站建设方案计划书网站外链的优化方法