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

阿里巴巴如何做网站公众号上传 wordpress

news 2025/11/3 22:37:09
阿里巴巴如何做网站,公众号上传 wordpress,网站开发工程师职位要求,wordpress pc6前言 看这篇文章前我建议你们先看这个视频还有这个视频，不然你们可能看不懂。 一、树状数组的核心思想与本质 核心思想：树状数组（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.yayakq.cn/news/817272/

相关文章：

  • 比较好的网站开发项目外贸网站海外推广
  • 网站建设首页需要哪些元素wordpress随机广告
  • 圣辉友联网站建设丰南建设网站
  • 重庆万州网站建设哪家好婚庆公司宣传文案
  • 网站关键词长度wordpress 4.5.2模板
  • 如何做自己的项目网站江苏建设信息电子证书
  • 门户网站架构响应式网站建设外文文献
  • 腾讯云点播做视频网站seo舆情优化
  • 想做个自己的网站user pro wordpress
  • 移动局域网ip做网站大连网站建设哪家好
  • 中国百科网vip钓鱼网站开发忻州网站制作
  • 沧州网站建设建站系统wordpress怎么改模版
  • 商务网站建设难不难wordpress做引导页
  • 好的手机端网站模板下载软件兰州企业网站制作
  • 自己做电视视频网站新乡网站优化公司价格
  • 连云港网站备案在哪营销网站建设网站设计
  • 建筑企业和建设企业区别四川网站seo设计
  • 阿勒泰建设招聘网站做网站网站内容怎么找
  • 做阿里巴巴网站上海手机网站建设
  • 织梦网站版权湖南土建网
  • 如今做那个网站致富建设企业银行登录
  • 网站建设结构总结网站特色怎么写
  • 兰州专业网站建设公司群晖wordpress设置
  • 国际型网站建设做网站如何备案
  • 商城类网站建设报价电商网站建设精英
  • 网站建设的架构设计大兴区网站建设公司
  • 嵊州网站不提供花架子网站 我
  • 台州网站建站公司北京最大做网站的公司有哪些
  • 重庆网站制作那家好做亚马逊外国网站需要语言好吗
  • 常德网站开发服务wordpress 管理登录